Construct Binary Tree from Preorder and Inorder Traversal
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given the preorder and inorder traversals of a tree (all values distinct), rebuild the tree.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which value is the root? It is always the first in preorder.
- Hint 2Where is that root in the inorder list? What is on each side of it?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You are given two lists about a family: the order in which people were announced at a function (each parent is announced before their children, left side before right) and the seating order from left to right. The first announced person is the head of the family. Finding him in the seating list shows who sits on his left (his left branch) and who sits on his right. Repeat for each branch.
- The obvious way
Search the inorder list for the root each time and copy sub-lists: O(n²) time and lots of copying.
- The key insight
Remember where each value sits in the inorder list (a dictionary). Walk through preorder one value at a time: the next value is the root of the tree for the current inorder window. Split the window at that value's inorder position: build the left part first, then the right part (that is the order preorder lists them).
- The algorithm
- Note each value's position in the inorder list.
- Take the next unused preorder value: it is the root of the current window.
- Build the left subtree from the part of the window left of the root's position.
- Then build the right subtree from the part on the right. Return the root.
Watch it run
Examplepreorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
First preorder value is 3: the root. In the seating list 3 splits [9] on its left from [15, 20, 7] on its right.
root 3; left window [9]; right window [15, 20, 7]
Where people slip
- Build the LEFT subtree before the right: preorder lists the left subtree's roots first.
- This needs all values distinct, otherwise the position lookup is ambiguous.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def build_tree(preorder, inorder):
where = {value: index for index, value in enumerate(inorder)} # value -> inorder position
next_root = iter(preorder) # roots, in preorder
def build(low, high): # the inorder window [low, high]
if low > high:
return None
value = next(next_root)
root = TreeNode(value)
middle = where[value]
root.left = build(low, middle - 1) # left part first (preorder order)
root.right = build(middle + 1, high)
return root
return build(0, len(inorder) - 1)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.