Rebuild From Pre-Order and In-Order Logs
MediumTrees
Problem
A debugging tool logged two traversals of a binary tree with distinct values: the pre-order sequence (node, left, right) and the in-order sequence (left, node, right).
Rebuild the tree from preorder and inorder and return its root.
Example 1
- Input:
- preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
- Output:
- [3, 9, 20, null, null, 15, 7]
3 is the root; in the in-order list, 9 is on its left and 15, 20, 7 on its right.
Example 2
- Input:
- preorder = [1, 2], inorder = [2, 1]
- Output:
- [1, 2]
Constraints
- 0 ≤ n ≤ 3000
- preorder and inorder are traversals of the same tree with distinct values.
- The tree height is at most 500.
Hint
Show the first hint
Which list tells you the root immediately, and which tells you how many nodes go to each side?
Walkthrough
How to approach it
01Clarify before coding
- Are values distinct? Yes, which makes the in-order position of each value unambiguous.
- Can the lists be empty? Yes: return an empty tree.
- Are the lists guaranteed consistent? Yes.
02Brute force
Recurse with sliced sub-arrays and find the root in inorder with a linear scan each time.
Cost: O(n²) time and memory in the worst case (a chain): each level scans and copies almost everything.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.