Construct Bst from Preorder Traversal
Given an array of distinct integers preorder that is the preorder traversal of a BST, construct the BST and return its root.
Constraints:
1 <= preorder.length <= 1001 <= preorder[i] <= 1000, all values are unique.
Intuition
1preorder = [8, 5, 1, 7, 10, 12]2
3 84 / \5 5 106 / \ \7 1 7 12Preorder is Root, Left, Right, so the first value is the root. After it come all the values of the left subtree (all smaller than the root) and then the right subtree (all larger). The left subtree ends exactly where the first value bigger than the root appears.
Searching for that split point for every node and slicing the array works but is O(n^2) in the worst case. We can do it in one pass by thinking in terms of upper bounds.
Approach: Build With an Upper Bound
Keep a single index i into the array, shared by all calls.
build(bound) creates the subtree for the next values in the array that are smaller than bound:
- If
iis past the end, orpreorder[i] > bound, this subtree is empty: returnnull. - Create the node from
preorder[i]and advancei. - Build its left subtree with the bound set to this node's value (everything in it must be smaller).
- Build its right subtree with the same bound we were given (it must be smaller than our ancestor's limit, but larger than this node, which the array order already guarantees).
- Return the node.
The initial bound is infinity. Each array element is consumed exactly once, so there is no searching or slicing.
Code
class Solution {int i = 0;TreeNode* build(vector<int>& preorder, int bound) {if (i == (int)preorder.size() || preorder[i] > bound) return nullptr;TreeNode* root = new TreeNode(preorder[i++]);root->left = build(preorder, root->val);root->right = build(preorder, bound);return root;}public:TreeNode* bstFromPreorder(vector<int>& preorder) {i = 0;return build(preorder, INT_MAX);}};
Complexity
Each array element is read exactly once and becomes exactly one node.
Recursion stack depth equals the tree height, which can be O(n) for a skewed input. The tree itself is the output.