The problem
You are given the pre-order list and the in-order list of a binary tree (lesson 2). All values are different. Rebuild the tree and return its root.
build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
# 3
# / \
# 9 20
# / \
# 15 7
The values are not sorted: this is any binary tree, not a search tree. Use the TreeNode class from the starter code.
Limits
- Up to 100,000 nodes; the tree is at most 300 levels deep, so recursion is fine.
Builds on TREE-3 Rebuilding a tree from traversals.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small tree | Not run | |
| 2 | Empty | Not run | |
| 3 | One node | Not run | |
| 4 | The lessons' tree | Not run | |
| 5 | Path to the left | Not run | |
| 6 | Path to the right | Not run | |
| 7 | Not a search tree | Not run | |
| 8 | 100,000 nodes | Not run |