Published on

# Restore binary tree

Authors

## 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:

`_5 1_5 / \_5 2 3_5 / / \_54 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

`_25solution(inorder, preorder) = {_25 "value": 1,_25 "left": {_25 "value": 2,_25 "left": {_25 "value": 4,_25 "left": null,_25 "right": null_25 },_25 "right": null_25 },_25 "right": {_25 "value": 3,_25 "left": {_25 "value": 5,_25 "left": null,_25 "right": null_25 },_25 "right": {_25 "value": 6,_25 "left": null,_25 "right": null_25 }_25 }_25}`
• For `inorder = [2, 5]` and `preorder = [5, 2]`, the output should be

`_9solution(inorder, preorder) = {_9 "value": 5,_9 "left": {_9 "value": 2,_9 "left": null,_9 "right": null_9 },_9 "right": null_9}`

## 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
`_3 1_3 / \_3build([4,2], [2,4]) build([5, 3, 6], [3, 5, 6])`
• Repeat step above and get new tree
`_5 1_5 / \_5 2 3_5 / \ / \_5 build([4],[4]) build([],[]) build([5],[5]) build([6],[6])`
• and the result is
`_5 1_5 / \_5 2 3_5 / / \_54 5 6`

Here the code:

`_36package main_36_36import "github.com/davecgh/go-spew/spew"_36_36type Tree struct {_36 Value interface{}_36 Left *Tree_36 Right *Tree_36}_36_36func build(inorder []int, preorder []int) *Tree {_36 if len(inorder) == 0 {_36 return nil_36 }_36_36 root := preorder[0]_36 rootIndex := 0_36_36 for i, val := range inorder {_36 if val == root {_36 rootIndex = i_36 break_36 }_36 }_36_36 return &Tree{_36 Value: root,_36 Left: build(inorder[:rootIndex], preorder[1:rootIndex+1]),_36 Right: build(inorder[rootIndex+1:], preorder[rootIndex+1:]),_36 }_36}_36_36func main() {_36 tree := build([]int{4, 2, 1, 5, 3, 6}, []int{1, 2, 4, 3, 5, 6})_36 spew.Dump(tree)_36}`