Katkat
Back

Reconstruct a BST from Preorder Traversal

LyftSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

Reconstruct the exact binary search tree represented by a preorder traversal of unique integers. Handle empty and completely skewed inputs at scale while preserving the intended tree rather than balancing it.

Problem

Given the preorder traversal of a binary search tree containing unique integers, reconstruct the tree and return its root.

Function Contract

Implement bstFromPreorder(preorder).

Constraints & Assumptions

  • 0 <= len(preorder) <= 100,000.
  • Values are unique signed 32-bit integers.
  • The input is guaranteed to be a valid preorder traversal of some BST.
  • Return null for an empty traversal.

Clarifying Questions to Ask

  • Are values unique? Yes.
  • Must the output tree be balanced? No; reproduce the represented BST.
  • Is sorting allowed? It is unnecessary and would lose the intended linear-time target.
  • Can the tree be completely skewed? Yes, so recursion depth matters.

Example

preorder = [8, 5, 1, 7, 10, 12]

result:
 8
 / \
 5 10
 / \ \
 1 7 12

Evaluation Focus

  • Consumes the traversal in one pass.
  • Attaches left and right children to the correct ancestors.
  • Handles monotonic input without recursion overflow.
  • Runs in O(n) time and O(h) auxiliary space.

Extensions to Discuss

  1. How would lower and upper bounds support a recursive construction?
  2. How would duplicates change the attachment rules?
  3. How could you validate an untrusted preorder while constructing?

Hints

Hint 1

Use unresolved ancestors: Maintain a stack of nodes whose right subtree has not yet been attached. A smaller value becomes the left child of the stack top; a larger value pops completed ancestors.

Hint 2

The last popped node is the parent: When a value is greater than several stack tops, its parent is the final ancestor removed before the stack becomes compatible.