Search Tree From a Pre-Order Log
MediumTrees
Problem
A binary search tree with distinct values was saved as its pre-order traversal (node, left subtree, right subtree). Only that one list survived.
Rebuild the tree from preorder and return its root. (For a search tree, pre-order alone is enough to determine the shape.)
Example 1
- Input:
- preorder = [8, 5, 1, 7, 10, 12]
- Output:
- [8, 5, 10, 1, 7, null, 12]
8 is the root; 5, 1, 7 are smaller and form the left subtree, 10, 12 the right.
Example 2
- Input:
- preorder = [1, 3]
- Output:
- [1, null, 3]
Constraints
- 1 ≤ preorder.length ≤ 10^4
- 1 ≤ preorder[i] ≤ 10^8
- The list is the pre-order of a valid search tree with distinct values.
Hint
Show the first hint
Given the root, how do you know where the left subtree ends in the list?
Walkthrough
How to approach it
01Clarify before coding
- Is the input a valid search-tree pre-order? Yes, so no validation is needed.
- Distinct values? Yes.
- Could it be a 10^4-long sorted list (a chain)? Yes, so avoid deep recursion.
02Brute force
Insert the values one by one into an empty search tree.
Cost: O(n·h): O(n²) for a sorted input, 5·10^7 steps for 10^4 values.
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.