1008. Construct Binary Search Tree from Preorder Traversal

Problem Description

Given an array of integers preorder, representing the preorder traversal of a Binary Search Tree (BST), construct the BST and return its root. A BST is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val. A preorder traversal visits a node before its left and right subtrees.

Solution: Recursive Depth-First Search (DFS)

The most efficient approach leverages the properties of preorder traversal and BSTs. Preorder traversal gives us the root node first. Since it's a BST, all nodes in the left subtree must be less than the root, and all nodes in the right subtree must be greater. This allows us to recursively build the tree.

Algorithm:

1. Base Case: If the input array is empty or the start index i exceeds the end index j, return null (representing an empty subtree).

2. Create Root: Create a new tree node with the value at preorder[i] (the root).

3. Partition: Find the index k where the values in preorder switch from being less than or equal to the root's value to being greater than the root's value. This index k separates the left and right subtrees. We can efficiently do this using binary search.

4. Recursive Calls: Recursively call the function to build the left subtree (preorder[i+1...k-1]) and the right subtree (preorder[k...j]).

5. Return Root: Return the newly constructed root node.

Time Complexity: O(n log n) - The binary search within the partition step takes O(log n) time in each recursive call, leading to a total time complexity of O(n log n). (Note: A slightly optimized approach using iterative partition would reduce this to O(n) in the average case.)

Space Complexity: O(n) - In the worst case (a skewed tree), the recursion depth can be O(n), leading to O(n) space complexity due to the call stack.

Code Implementation (Python)

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]) -> TreeNode:
        def build(i, j):
            if i > j:
                return None
            root = TreeNode(preorder[i])
            k = i + 1
            while k <= j and preorder[k] <= preorder[i]:
                k += 1
            root.left = build(i + 1, k - 1)
            root.right = build(k, j)
            return root
        return build(0, len(preorder) - 1)

This Python code directly implements the algorithm described above. The build function recursively constructs the tree, using binary search implicitly in the while loop to find the partitioning point k.

Code Implementation (Java)

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    private int[] preorder;
 
    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder = preorder;
        return build(0, preorder.length - 1);
    }
 
    private TreeNode build(int i, int j) {
        if (i > j) return null;
        TreeNode root = new TreeNode(preorder[i]);
        int k = i + 1;
        while (k <= j && preorder[k] <= preorder[i]) k++;
        root.left = build(i + 1, k - 1);
        root.right = build(k, j);
        return root;
    }
}

The Java code mirrors the Python solution's structure and logic.

Other languages (C++, JavaScript, Go, etc.) can implement the same algorithm with minor syntactic differences. The core recursive approach and binary search based partition remain the same.