Problem

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree 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 of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Examples

Example 1:

graph TB 
    8 --> 5 & 10
    5 --> 1 & 7
    10 --> null & 12
  
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Example 2:

Input: preorder = [1,3]
Output: [1,null,3]

Solution

Method 1 - Recursion

The given preorder array can be used to construct the BST by using a recursive approach. Keep track of left and right indices instead of slicing the whole array. Starting from the first element as the root, we recursively determine the left and right subtrees by finding the separation point in the preorder array where elements start being greater than the root value.

Approach

  1. Initialize Root: The first element in preorder is the root.
  2. Recursive Construction:
    • Use a helper function buildBST(left, right) that constructs the tree from preorder[left ... right].
    • Base case: If left > right, return None.
    • Create a root node with preorder[left].
    • Find the first index where elements are greater than preorder[left].
    • Recursively build the left and right subtrees.
  3. Return Root: Start the recursive construction from the entire range of the array.

Code

Java
public class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        return buildBST(preorder, 0, preorder.length - 1);
    }

    private TreeNode buildBST(int[] preorder, int left, int right) {
        if (left > right) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[left]);
        int pointer = left;
        while (pointer + 1 <= right && preorder[pointer + 1] < root.val) {
            pointer++;
        }

        root.left = buildBST(preorder, left + 1, pointer);
        root.right = buildBST(preorder, pointer + 1, right);

        return root;
    }
}
Python
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional['Solution.TreeNode']:
        def buildBST(left: int, right: int) -> Optional['Solution.TreeNode']:
            if left > right:
                return None

            root_val = preorder[left]
            root = Solution.TreeNode(root_val)
            
            pointer = left
            while pointer + 1 <= right and preorder[pointer + 1] < root_val:
                pointer += 1
            
            left_tree = buildBST(left + 1, pointer)
            right_tree = buildBST(pointer + 1, right)

            root.left = left_tree
            root.right = right_tree

            return root

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

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the preorder list. Each element is processed once.
  • 🧺 Space complexity: O(h), where h is the height of the tree due to the recursive call stack. In the worst case (skewed tree), it can be O(n).

Method 2 - Iterative Using Stack

The given preorder array can be used to construct the BST by maintaining a stack to keep track of nodes. Starting from the first element as the root, we iteratively determine the position for each subsequent node by comparing it with the top of the stack.

Approach

  1. Initialize Root: The first element in preorder is the root.
  2. Stack Usage:
    • Use a stack to keep track of nodes.
    • If the current value is less than the stack’s top value, it is the left child of the stack’s top node.
    • Otherwise, pop from the stack until you find a node smaller than the current value. The current value is the right child of the last popped node.
    • Push the current node to the stack.
  3. Return Root: After processing all the elements, return the root node.

Code

Java
public class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        for (int i = 1; i < preorder.length; i++) {
            TreeNode node = new TreeNode(preorder[i]);
            if (preorder[i] < stack.peek().val) {
                stack.peek().left = node;
            } else {
                TreeNode parent = stack.peek();
                while (!stack.isEmpty() && preorder[i] > stack.peek().val) {
                    parent = stack.pop();
                }
                parent.right = node;
            }
            stack.push(node);
        }
        return root;
    }
}
Python
class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional['Solution.TreeNode']:
        if not preorder:
            return None

        root = Solution.TreeNode(preorder[0])
        stack = [root]

        for value in preorder[1:]:
            node = Solution.TreeNode(value)
            if value < stack[-1].val:
                stack[-1].left = node
            else:
                parent = stack[-1]
                while stack and value > stack[-1].val:
                    parent = stack.pop()
                parent.right = node
            stack.append(node)

        return root

Complexity

  • ⏰ Time complexity: (n), where n is the number of elements in the preorder list.
  • 🧺 Space complexity: O(n) due to the usage of the stack.