LeetCode 1008 - Construct Binary Search Tree from Preorder Traversal

Difficulty: 🟡 Medium
Topics: Array, Stack, Tree, Binary Search Tree, Monotonic Stack, Binary Tree

Solution

Let's dive deep and construct a thorough technical guide for LeetCode 1008, following your formatting rules.

Problem Understanding

The problem asks us to construct a binary search tree (BST) from a given preorder traversal array. A preorder traversal is defined as visiting the root node first, then recursively visiting the left subtree, followed by the right subtree. In a BST, for every node, values in the left subtree are strictly less than the node's value, and values in the right subtree are strictly greater.

The input preorder is a list of unique integers representing the preorder traversal of a BST. Our task is to reconstruct the BST and return its root node. For example, given [8,5,1,7,10,12], the first value 8 becomes the root, then 5 is placed in the left subtree, 10 in the right subtree, and so on.

Constraints indicate that preorder has at most 100 elements with values from 1 to 1000. All values are unique, which simplifies handling duplicates.

Important edge cases include very small arrays (length 1 or 2), strictly increasing or decreasing sequences (creating skewed trees), and arrays that may result in nodes having only one child. The problem guarantees that a valid BST exists for any input array.

Approaches

Brute Force

A straightforward approach is to recursively insert each element of preorder into the BST. Start with the first element as the root. For every subsequent value, traverse the tree from the root, comparing values until the correct insertion point is found. This works because inserting values into a BST in preorder order naturally preserves BST properties.

However, this approach is inefficient because each insertion could take up to O(n) time if the tree is skewed, leading to a worst-case time complexity of O(n²). This is unnecessary overhead for larger inputs.

Optimal Approach

The key observation is that the preorder traversal inherently provides a monotonic property for left and right subtrees. The first element is the root. All subsequent elements smaller than the root belong to the left subtree, and the first element greater than the root marks the beginning of the right subtree. Using this property, we can build the tree efficiently using either recursion with bounds or a stack-based monotonic approach.

A stack-based approach efficiently constructs the BST in O(n) time. We iterate through preorder, maintaining a stack of ancestors. For each new value, we find its parent by popping from the stack until the top has a value greater than the current node. This ensures correct placement in the BST.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Insert each node into BST sequentially, inefficient for skewed trees
Optimal	O(n)	O(n)	Stack-based construction or recursion with bounds, linear scan ensures correct placement

Algorithm Walkthrough

Initialize an empty stack to track the path from the root to the current node.
Take the first element of preorder as the root node and push it onto the stack.
Iterate through the remaining elements of preorder.
For each element, create a new node.
If the element is less than the top of the stack, it becomes the left child of the stack's top node. Push it onto the stack.
If the element is greater than the top of the stack, pop nodes from the stack until the top node has a value greater than the element. The last popped node becomes the parent, and the new node is its right child. Push the new node onto the stack.
Continue until all elements are processed. Return the root.

Why it works: The stack maintains the path from the root to the current insertion point. By popping nodes until finding a suitable parent, we ensure the BST property is preserved, and each node is placed correctly in its left or right subtree. This guarantees the correct reconstruction of the BST from preorder traversal.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> 'Optional[TreeNode]':
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        stack = [root]
        
        for value in preorder[1:]:
            node = TreeNode(value)
            if value < stack[-1].val:
                stack[-1].left = node
            else:
                parent = None
                while stack and stack[-1].val < value:
                    parent = stack.pop()
                parent.right = node
            stack.append(node)
        
        return root

The Python implementation initializes the root and stack, then iterates through the preorder list. For each value, it determines whether to attach the node as a left or right child based on the stack's state. Popping from the stack ensures the correct parent is found for right children, preserving BST properties.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstFromPreorder(preorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    
    root := &TreeNode{Val: preorder[0]}
    stack := []*TreeNode{root}
    
    for _, val := range preorder[1:] {
        node := &TreeNode{Val: val}
        if val < stack[len(stack)-1].Val {
            stack[len(stack)-1].Left = node
        } else {
            var parent *TreeNode
            for len(stack) > 0 && stack[len(stack)-1].Val < val {
                parent = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
            }
            parent.Right = node
        }
        stack = append(stack, node)
    }
    
    return root
}

The Go implementation mirrors Python closely. Slice manipulation is used for the stack, and nil represents empty child pointers. The logic for finding the parent node is the same, maintaining correctness.

Worked Examples

Example 1: `[8,5,1,7,10,12]`

Step	Stack (top → bottom)	Action
1	[8]	Initialize root 8
2	[8,5]	5 < 8 → left child of 8
3	[8,5,1]	1 < 5 → left child of 5
4	[8,5,7]	7 > 1 → pop 1, 7 > 5 → pop 5 → 7 becomes right child of 5
5	[8,10]	10 > 7 → pop 7, 10 > 8 → pop 8 → 10 becomes right child of 8
6	[10,12]	12 > 10 → right child of 10

Example 2: `[1,3]`

Step	Stack	Action
1	[1]	root 1
2	[1,3]	3 > 1 → pop 1 → 3 becomes right child of 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is pushed and popped from the stack exactly once
Space	O(n)	Stack may store up to n nodes in the worst case (completely skewed tree)

The linear time complexity arises because each node is processed exactly once and involves at most a constant number of stack operations. The space is dominated by the stack.

Test Cases

# test cases
assert Solution().bstFromPreorder([8,5,1,7,10,12]).val == 8  # standard case
assert Solution().bstFromPreorder([1,3]).val == 1  # minimal two-element tree
assert Solution().bstFromPreorder([5]).val == 5  # single-node tree
assert Solution().bstFromPreorder([1,2,3,4,5]).val == 1  # strictly increasing → right skew
assert Solution().bstFromPreorder([5,4,3,2,1]).val == 5  # strictly decreasing → left skew
assert Solution().bstFromPreorder([2,1,3]).val == 2  # balanced small tree

Test	Why
`[8,5,1,7,10,12]`	Standard complex BST reconstruction
`[1,3]`	Small BST with only right child
`[5]`	Edge case: single-node tree
`[1,2,3,4,5]`	Right-skewed tree
`[5,4,3,2,1]`	Left-skewed tree
`[2,1,3]`	Balanced small tree

Edge Cases

One edge case is a single-node array like [5]. This tests if the algorithm can handle minimal input. Our implementation correctly initializes the root and returns it without further stack operations