#1008

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Construct Binary Search Tree from Preorder Traversal

Construct a binary search tree directly from a preorder traversal array using stack-based state tracking efficiently.

array stack tree binary search tree monotonic stack

Problem Statement

Given an array of unique integers representing the preorder traversal of a binary search tree, construct and return the root node of the corresponding BST. Ensure that for each node, all values in its left subtree are strictly less and all values in its right subtree are strictly greater than the node's value.

The input array always allows the construction of a valid BST. The tree must be reconstructed while maintaining the exact preorder insertion order, reflecting the precise structure implied by the traversal sequence.

Examples

Example 1

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

Output: [8,5,10,1,7,null,12]

Example details omitted.

Example 2

Input: preorder = [1,3]

Output: [1,null,3]

Example details omitted.

Constraints

1 <= preorder.length <= 100
1 <= preorder[i] <= 1000
All the values of preorder are unique.

Solution Approach

Recursive Bounds-Based Insertion

Use recursion with lower and upper bounds to place each node. Maintain an index pointer to traverse the preorder array, creating nodes only if the current value fits within the subtree's bounds. This approach ensures the BST property while directly following preorder ordering.

Iterative Stack Simulation

Maintain a stack to track ancestors of the current node. For each value, pop from the stack until finding the correct parent, then insert as a left or right child. This method avoids recursion, efficiently tracking state and preserving the BST structure.

Optimized Single-Pass Construction

Combine the bounds approach with stack optimization to construct the BST in one pass. Each value is placed using current ancestors from the stack, ensuring O(n) time and minimal auxiliary space. This reduces overhead compared to naive recursive solutions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n) for iterative or optimized recursive approaches to potentially O(n^2) if naive insertion is used. Space complexity is O(h) for recursion or stack, where h is the height of the BST, up to O(n) in the worst case.

What Interviewers Usually Probe

Watch for correct placement of nodes respecting BST property for left and right subtrees.
Expect candidates to optimize recursive calls or avoid unnecessary stack growth.
Check handling of edge cases with minimal or maximal preorder values.

Common Pitfalls or Variants

Common pitfalls

Inserting nodes without validating BST bounds can violate tree structure.
Mismanaging stack updates can lead to incorrect parent-child assignments.
Assuming preorder order directly maps to left-right placement without bound checks.

Follow-up variants

Construct BST from postorder traversal instead of preorder, reversing insertion logic.
Rebuild a BST given both inorder and preorder arrays for precise reconstruction.
Determine the height of the BST while constructing it from preorder traversal.

FAQ

What is the main challenge in Construct Binary Search Tree from Preorder Traversal?

The challenge is inserting nodes in preorder order while maintaining BST properties, requiring careful state tracking of ancestors.

Can this BST construction be done iteratively?

Yes, using a stack to track parent nodes, each preorder value can be placed in the correct position without recursion.

What is the time complexity of building the BST from preorder?

Optimal approaches achieve O(n) time, visiting each node once, while naive insertion may lead to O(n^2) in worst cases.

Are all values in the preorder array unique?

Yes, uniqueness is guaranteed, simplifying insertion logic since no duplicate handling is needed.

How does the bounds method prevent incorrect BST construction?

By maintaining lower and upper limits for valid node placement, each value is only inserted where it respects BST constraints, ensuring correct tree structure.

terminal

Solution

Solution 1: DFS + Binary Search

We design a function $\textit{dfs}(i, j)$ to construct a binary search tree from the nodes $\textit{preorder}[i]$ to $\textit{preorder}[j]$. The answer is $\textit{dfs}(0, n - 1)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        def dfs(i: int, j: int) -> Optional[TreeNode]:
            if i > j:
                return None
            root = TreeNode(preorder[i])
            l, r = i + 1, j + 1
            while l < r:
                mid = (l + r) >> 1
                if preorder[mid] > preorder[i]:
                    r = mid
                else:
                    l = mid + 1
            root.left = dfs(i + 1, l - 1)
            root.right = dfs(l, j)
            return root

        return dfs(0, len(preorder) - 1)

Continue Practicing

#654 maximum binary tree #897 increasing order search tree #1569 number of ways to reorder array to get same bst