On this page

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 <= 100
  • 1 <= preorder[i] <= 1000, all values are unique.

Intuition

1preorder = [8, 5, 1, 7, 10, 12]
2
3 8
4 / \
5 5 10
6 / \ \
7 1 7 12

Preorder 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:

  1. If i is past the end, or preorder[i] > bound, this subtree is empty: return null.
  2. Create the node from preorder[i] and advance i.
  3. Build its left subtree with the bound set to this node's value (everything in it must be smaller).
  4. 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).
  5. 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

Time: O(n)

Each array element is read exactly once and becomes exactly one node.

Space: O(h)

Recursion stack depth equals the tree height, which can be O(n) for a skewed input. The tree itself is the output.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The first value of a preorder is the root, and the following values split into smaller ones for the left subtree and larger ones for the right. Searching for the split every time is O of n squared, so I use an upper bound instead. I keep one shared index. My build function takes a bound. If the index is out of range or the current value is above the bound, that subtree is empty. Otherwise I create a node from the current value, advance the index, build the left subtree with this node's value as the bound, and build the right subtree with the bound I received. Each element is consumed once, so time is O of n and space is O of h for the recursion."
Next TopicInorder Successor in Bst