Restore binary tree

Restore binary tree

February 14, 2023

Name
Moch Lutfi
@kaptenupi

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]` and `preorder = [1, 2, 4, 3, 5, 6]`, the output should be

`solution(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]` and `preorder = [5, 2]`, the output should be

`solution(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 contains `1`. We got index `2` 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)