Construct Binary Search Tree from Preorder
Medium · Trees · Array · Stack · Tree · Binary Search Tree · Monotonic Stack · Binary Tree
Problem
Given an array preorder of distinct integers that is the preorder traversal of a binary search tree, build that tree and return its root.
Preorder visits a node first, then its left subtree, then its right subtree. In a binary search tree every value in a node's left subtree is smaller than the node and every value in its right subtree is larger. The input always comes from a valid binary search tree, and that tree is unique.
Examples
Input: preorder = [9,4,2,6,15,20] Output: [9,4,15,2,6,null,20]
9 is the root; 4, 2 and 6 are smaller and form its left subtree; 15 and 20 form the right.
Input: preorder = [3,2,1] Output: [3,2,null,1]
Each value is smaller than the one before, giving a chain of left children.
Input: preorder = [1,3] Output: [1,null,3]
3 is larger than 1, so it is the right child.
Constraints
- 1 <= len(preorder) <= 100
- 1 <= preorder[i] <= 1000
- All values are distinct
- preorder is the preorder of some binary search tree
Approaches
- Insert the values one by one — time O(n²), space O(1) extra
Follow-up
Can you do it without recursion? Keep a stack of nodes whose right child may still be filled: pop while the top is smaller than the new value; the last popped node takes it as a right child, otherwise the top takes it as a left child.
Related problems
Start free on Cariara · Coding problems · System design studio
