Code Implementation

# 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):
        self.i = 0
        def helper(bound=float('inf')):
            if self.i == len(preorder) or preorder[self.i] > bound:
                return None
            root = TreeNode(preorder[self.i])
            self.i += 1
            root.left = helper(root.val)
            root.right = helper(bound)
            return root
        return helper()
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int i = 0;
    TreeNode* helper(vector& preorder, int bound) {
        if (i == preorder.size() || preorder[i] > bound) return nullptr;
        TreeNode* root = new TreeNode(preorder[i++]);
        root->left = helper(preorder, root->val);
        root->right = helper(preorder, bound);
        return root;
    }
    TreeNode* bstFromPreorder(vector& preorder) {
        return helper(preorder, INT_MAX);
    }
};
      

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    int i = 0;
    public TreeNode bstFromPreorder(int[] preorder) {
        return helper(preorder, Integer.MAX_VALUE);
    }
    private TreeNode helper(int[] preorder, int bound) {
        if (i == preorder.length || preorder[i] > bound) return null;
        TreeNode root = new TreeNode(preorder[i++]);
        root.left = helper(preorder, root.val);
        root.right = helper(preorder, bound);
        return root;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var bstFromPreorder = function(preorder) {
    let i = 0;
    function helper(bound = Infinity) {
        if (i === preorder.length || preorder[i] > bound) return null;
        let root = new TreeNode(preorder[i++]);
        root.left = helper(root.val);
        root.right = helper(bound);
        return root;
    }
    return helper();
};
      

Problem Description

You are given an array preorder representing the preorder traversal of a binary search tree (BST). Your task is to construct the BST from this traversal and return its root node.

• Each element in preorder is unique and must be used exactly once.
• There is exactly one valid BST that can be built from the given preorder traversal.
• You must not reuse elements or change their order.

The constructed tree must satisfy the BST property: for any node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have larger values.

Thought Process

The problem requires us to rebuild a BST given its preorder traversal. Preorder means we visit the root first, then left subtree, then right subtree. Since all elements are unique and the BST is valid, there is only one way to reconstruct the tree.

A brute-force approach might try to insert each value into the BST one by one, simulating the insertion process. However, this can be inefficient, especially if the tree is skewed.

An optimized approach leverages the properties of preorder traversal and BSTs: the first value is always the root, and all subsequent values less than the root must be in the left subtree, while the rest belong to the right subtree. We can use recursion with bounds to efficiently build the tree in a single pass.

Solution Approach

We use a recursive helper function to construct the tree by maintaining an index into the preorder array and a bound for allowed node values.

1. Initialize: Start with an index at 0. The first element is the root.
2. Recursive Construction: For each recursive call, check if the current value is within the allowed bound (all values in the left subtree must be less than the parent, all in the right must be greater).
3. Advance Index: When a node is created, increment the index so the next call processes the next value.
4. Left and Right Subtrees: The left subtree is constructed with the current node's value as the new upper bound. The right subtree uses the previous bound.
5. Base Case: If the index is out of bounds or the value is greater than the allowed bound, return null.

This approach guarantees each node is placed correctly in a single pass through the array, with no need to search for subtree boundaries explicitly.

Example Walkthrough

Let's walk through the process with the input preorder = [8, 5, 1, 7, 10, 12]:

1. Start: Index 0, value 8. Create root node 8.
2. Left Subtree of 8: Next value is 5 (less than 8). Create left child 5.
3. Left Subtree of 5: Next value is 1 (less than 5). Create left child 1.
4. Left Subtree of 1: Next value is 7 (greater than 1), so left child is null.
5. Right Subtree of 1: 7 is still less than 5, so right child is null.
6. Right Subtree of 5: 7 (less than 8, greater than 5). Create right child 7.
7. Left and Right of 7: Next value is 10 (greater than 7), so both children are null.
8. Right Subtree of 8: 10 (greater than 8). Create right child 10.
9. Left of 10: 12 (greater than 10), so left child is null.
10. Right of 10: 12 (greater than 10). Create right child 12.
11. Left/Right of 12: No more elements, so both are null.

The resulting tree structure matches the correct BST for the input preorder traversal.

Time and Space Complexity

• Brute-force Approach: Inserting each node into the BST one by one can take up to O(N^2) time in the worst case (e.g., skewed tree).
• Optimized Approach: The recursive solution visits each node exactly once, so the time complexity is O(N).
• Space Complexity: The space used is O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N; in the best case (balanced tree), H = log N.

Summary

By leveraging the properties of preorder traversal and BSTs, we can construct the tree efficiently in a single pass using recursion and bounds. This approach avoids unnecessary repeated searches or insertions, making it both elegant and efficient. The key insight is to use the preorder order and value bounds to determine subtree boundaries without scanning the array multiple times.