Construct BST from Preorder Traversal

MediumTreesbst

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an integer array preorder holding the preorder traversal (node, then left subtree, then right subtree) of a binary search tree with **distinct** values. Rebuild the BST and return its root. A BST requires every value in a node's left subtree to be strictly smaller than the node and every value in its right subtree to be strictly larger. Exactly one BST has a given preorder traversal, so the answer is unique. It is graded by its level-order serialization. Inserting each value one by one works in O(n^2) for skewed input; passing value bounds down the recursion gives O(n).

Examples

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 form the right subtree.
Input: preorder = [1,3]
Output: [1,null,3]
3 is larger than 1, so it becomes the right child.

Constraints

  • 1 <= preorder.length <= 1000
  • 1 <= preorder[i] <= 10^8
  • All values are distinct
  • `preorder` is a valid BST preorder traversal

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bst problems