Rebuild a tree from two walks
Recreate a binary tree from its preorder and inorder lists, by taking each root from the preorder list and using the inorder list to split the left side from the right. About 20 minutes.
Roots from one list, sides from the other
Preorder visits the root, then the left subtree, then the right subtree. So its first value is the root. Inorder visits the left subtree, then the root, then the right subtree, so the root splits it: everything before the root is on the left, everything after is on the right.
Take the first preorder value as root, find it in the inorder list, and you know both sides.
pos = {v: i for i, v in enumerate(inorder)}
mid = pos[3] # where 3 sits in inorder- left
- [2, 4, 6]
- right
- [10]
The first preorder value, 8, is the root. In the inorder list, 2, 4, 6 are left of it and 10 is right of it.
Left first, using a range
Describe each piece of the tree by a range of positions in the inorder list. The whole tree is the whole range. After picking the root at position mid, the left subtree is the range up to mid minus one, and the right is the range from mid plus one.
Build the left subtree before the right, because the preorder list lists the left subtree's values first. An empty range means an empty subtree. A map from each value to its inorder position makes finding mid immediate.
# nodes on the left left_size = mid - lo right_size = hi - mid
Preorder starts with 8, and inorder is 4, 6, 8, 10. What is on the left of the root?
- A4 and 6
- B10
- CNothing
Show the answer
4 and 6. In the inorder list, everything before the root 8 is in its left subtree.
Construct binary tree from preorder and inorder traversal
Given two integer arrays preorder and inorder, the preorder and inorder traversals of the same binary tree whose node values are all different, construct the tree and return its root.
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7] → [3, 9, 20, null, null, 15, 7]
0 ≤ length ≤ 3,000 · all values are different · both arrays describe the same tree