Restore binary tree
February 14, 2023
Problem
Let's define inorder and preorder traversals of a binary tree as follows:
- Inorder traversal first visits the left subtree, then the root, then its right subtree;
- Preorder traversal first visits the root, then its left subtree, then its right subtree.
For example, if tree looks like this:
1 / \ 2 3 / / \4 5 6
then the traversals will be as follows:
- Inorder traversal:
[4, 2, 1, 5, 3, 6]
- Preorder traversal:
[1, 2, 4, 3, 5, 6]
Given the inorder and preorder traversals of a binary tree t
, but not t
itself, restore t
and return it.
Example
-
For
inorder = [4, 2, 1, 5, 3, 6]
andpreorder = [1, 2, 4, 3, 5, 6]
, the output should besolution(inorder, preorder) = {"value": 1,"left": {"value": 2,"left": {"value": 4,"left": null,"right": null},"right": null},"right": {"value": 3,"left": {"value": 5,"left": null,"right": null},"right": {"value": 6,"left": null,"right": null}}} -
For
inorder = [2, 5]
andpreorder = [5, 2]
, the output should besolution(inorder, preorder) = {"value": 5,"left": {"value": 2,"left": null,"right": null},"right": null}
Solution
- The first element in the preorder array is always the root node of the tree.
- We find the index of this root node in the inorder array.
- All the elements to the left of the root node in the inorder array are in the left subtree, and all the elements to the right of the root node in the inorder array are in the right subtree.
- We recursively call the buildTree function on the left and right subtrees, passing the appropriate inorder and preorder arrays for each subtree.
Dry Run
For inorder = [4, 2, 1, 5, 3, 6]
and preorder = [1, 2, 4, 3, 5, 6]
- Get root from first element in the preorder array
1
then get index from inorder that contains1
. We got index2
here. - Create tree recursively
1 / \build([4,2], [2,4]) build([5, 3, 6], [3, 5, 6])
- Repeat step above and get new tree
1 / \ 2 3 / \ / \ build([4],[4]) build([],[]) build([5],[5]) build([6],[6])
- and the result is
1 / \ 2 3 / / \4 5 6
Here the code:
package mainimport "github.com/davecgh/go-spew/spew"type Tree struct { Value interface{} Left *Tree Right *Tree}func build(inorder []int, preorder []int) *Tree { if len(inorder) == 0 { return nil } root := preorder[0] rootIndex := 0 for i, val := range inorder { if val == root { rootIndex = i break } } return &Tree{ Value: root, Left: build(inorder[:rootIndex], preorder[1:rootIndex+1]), Right: build(inorder[rootIndex+1:], preorder[rootIndex+1:]), }}func main() { tree := build([]int{4, 2, 1, 5, 3, 6}, []int{1, 2, 4, 3, 5, 6}) spew.Dump(tree)}
Try it your self https://go.dev/play/p/dFSASO4Js4c (opens in a new tab)