Restore binary tree

February 14, 2023

Name: Moch Lutfi
Twitter: @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:

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

Here the code:

package main
import "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)

Find substring Fibonacci with dynamic programming