Construct Binary Search Tree from Preorder Traversal

• The core idea is to use recursion. The first element in any preorder traversal sequence is the root of the tree/subtree.
• Create a recursive function, say build(preorder, start, end), which constructs a BST from the subarray preorder[start...end].
• The base case for the recursion is when start > end, which means the subarray is empty, so we return null.
• In the recursive step, create a new TreeNode with the value preorder[start]. This is the root of the current subtree.
• Iterate from start + 1 to end to find the index of the first element that is greater than root.val. Let's call this splitIndex.
• All elements from start + 1 to splitIndex - 1 belong to the left subtree.
• All elements from splitIndex to end belong to the right subtree.
• Make a recursive call to build the left subtree: root.left = build(preorder, start + 1, splitIndex - 1).
• Make another recursive call to build the right subtree: root.right = build(preorder, splitIndex, end).
• Return the root.

The implementation uses a recursive helper function that operates on a specific range of the preorder array, defined by start and end indices. For each recursive call, the first element preorder[start] is taken as the root. Then, a linear scan is performed on the rest of the range [start + 1, end] to find the boundary between the left and right subtrees. This boundary is the first element that is larger than the root's value. Once found, two more recursive calls are made for the left and right sub-ranges.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode bstFromPreorder(int[] preorder) {18        if (preorder == null || preorder.length == 0) {19            return null;20        }21        return build(preorder, 0, preorder.length - 1);22    }23 24    private TreeNode build(int[] preorder, int start, int end) {25        if (start > end) {26            return null;27        }28        TreeNode root = new TreeNode(preorder[start]);29        30        int splitIndex = start + 1;31        while (splitIndex <= end && preorder[splitIndex] < root.val) {32            splitIndex++;33        }34        35        root.left = build(preorder, start + 1, splitIndex - 1);36        root.right = build(preorder, splitIndex, end);37        38        return root;39    }40}

• Initialize the root of the tree with the first element of preorder.
• Use a Stack to keep track of the path of ancestors. Push the root onto the stack.
• Iterate through the preorder array from the second element (i = 1).
• For each element preorder[i], create a new child node.
• Let parent be the node at the top of the stack.
• If child.val < parent.val, the child is the left child of parent. So, set parent.left = child.
• If child.val > parent.val, the child is the right child of some ancestor. We need to find the correct parent by popping from the stack. Pop nodes as long as the stack is not empty and child.val is greater than the value of the node at the top of the stack. The last node that was at the top of the stack before the condition failed (or the last node popped) is the parent. Set parent.right = child.
• After placing the child, push it onto the stack.
• After the loop finishes, return the root.

We start by creating the root from preorder[0] and pushing it to a stack. Then, we iterate through the rest of the preorder array. For each new value, we create a node. We check the node at the top of the stack. If the new node's value is smaller, it's a left child. If it's larger, we pop from the stack until we find a node that is a suitable parent (i.e., the new node's value is smaller than the node at the top of the stack, or the stack becomes empty). The last popped node becomes the parent, and the new node is its right child. Finally, the new node is pushed onto the stack to extend the current path.

1class Solution {2    public TreeNode bstFromPreorder(int[] preorder) {3        if (preorder == null || preorder.length == 0) {4            return null;5        }6        TreeNode root = new TreeNode(preorder[0]);7        Stack<TreeNode> stack = new Stack<>();8        stack.push(root);9 10        for (int i = 1; i < preorder.length; i++) {11            TreeNode node = new TreeNode(preorder[i]);12            TreeNode parent = stack.peek();13            14            if (node.val < parent.val) {15                parent.left = node;16            } else {17                while (!stack.isEmpty() && node.val > stack.peek().val) {18                    parent = stack.pop();19                }20                parent.right = node;21            }22            stack.push(node);23        }24        return root;25    }26}

• Use a global index preorderIndex to track the current element in the preorder array.
• Define a recursive helper function build(lower, upper) that constructs a subtree whose nodes must have values within the range (lower, upper).
• The initial call is build(Integer.MIN_VALUE, Integer.MAX_VALUE).
• Inside build(lower, upper):
  • If preorderIndex is at the end of the array, return null.
  • Get the current value val = preorder[preorderIndex].
  • If val is not within the (lower, upper) bounds, it doesn't belong in this subtree, so return null.
  • If the value is valid, increment preorderIndex.
  • Create a new TreeNode with val. This is the root of the current subtree.
  • Recursively build the left subtree by calling build(lower, val). The upper bound for the left child is the parent's value.
  • Recursively build the right subtree by calling build(val, upper). The lower bound for the right child is the parent's value.
  • Return the root.

The core of this method is a recursive function that builds the tree while respecting the BST property. We maintain a global index for the preorder array. The recursive function is given a lower and upper bound for the values of nodes it can create. When we process an element from preorder, we check if it falls within the current bounds. If it does, we create a node, advance the index, and then make two recursive calls for the left and right children, updating the bounds accordingly. For the left child, the new upper bound is the parent's value. For the right child, the new lower bound is the parent's value. If an element doesn't fit the bounds, we know that branch of the tree is empty, and we return null.

1class Solution {2    private int preorderIndex = 0;3    private int[] preorder;4 5    public TreeNode bstFromPreorder(int[] preorder) {6        this.preorder = preorder;7        return build(Integer.MIN_VALUE, Integer.MAX_VALUE);8    }9 10    private TreeNode build(int lower, int upper) {11        if (preorderIndex == preorder.length) {12            return null;13        }14 15        int val = preorder[preorderIndex];16        if (val < lower || val > upper) {17            return null;18        }19 20        preorderIndex++;21        TreeNode root = new TreeNode(val);22        root.left = build(lower, val);23        root.right = build(val, upper);24        return root;25    }26}