PPractick

The problem

A config service stores a BST as just its preorder sequence and must rebuild the exact tree. For a BST, preorder alone is enough, because the ordering tells each value where it belongs. Inserting the values one by one works but is O(n²) on skewed trees. The O(n) method passes an upper bound: each call builds a subtree from the next preorder values as long as they're below the bound. A node's left subtree uses the node's own value as its bound, and its right subtree inherits the parent's bound.

Example: [8, 5, 1, 7, 10, 12] → [8, 5, 10, 1, 7, null, 12].

Function signature

TreeNode* bstFromPreorder(const vector<int>& preorder);  // distinct values

Test cases

Input (preorder)	Output (level order)	Explanation
[8, 5, 1, 7, 10, 12]	[8, 5, 10, 1, 7, null, 12]
[4, 2, 1, 3, 6, 5, 7]	[4, 2, 6, 1, 3, 5, 7]
[1, 3]	[1, null, 3]
[5]	[5]
[]	[]

(Confirm: values are distinct and the sequence is a valid BST preorder.)

How interviewers phrase it

• "Given an array of integers preorder, which represents the preorder traversal of a BST, construct the tree and return its root" (LeetCode 1008).

Clarifying questions to ask

1. Are values distinct? (Yes.)
2. Is the input guaranteed to be a valid BST preorder? (Yes.)
3. Is O(n log n) or O(n²) acceptable? (O(n) is the goal.)

Follow-ups to expect

1. "Why is preorder enough for a BST, when a general tree needs inorder too?"
2. "Simplest approach?"
3. "How does the bound give O(n)?"
4. "Monotonic-stack alternative?"
5. "Complexity?"

Related questions

• Sort a stack using recursion Medium
• Reverse a Stack Medium
• Insert a given node in BST Medium
• Delete a node in BST Medium
• Check if a tree is a BST or not Medium
• LCA in BST Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in