Construct Binary Search Tree from Preorder Traversal

Problem Description

Given an array of integers representing the preorder traversal of a Binary Search Tree (BST), the task is to construct the BST and return its root.

Naive Approach

A straightforward approach is to iterate through the preorder array and insert each element into the BST. The insertion process ensures that the BST properties are maintained at each step.

Algorithm:

1. Create a TreeNode class to represent nodes in the BST.
2. Implement an insert function that takes the root of the BST and a value to insert as input.
3. For each value in the preorder array, insert it into the BST starting from the root. If the root is null, create a new node and make it the root.

Code (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 {
    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = null;
        for (int val : preorder) {
            root = insert(root, val);
        }
        return root;
    }

    private TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insert(root.left, val);
        } else {
            root.right = insert(root.right, val);
        }
        return root;
    }
}

Time Complexity: O(N^2) in the worst case (skewed tree), where N is the number of nodes. Each insertion can take O(N) in the worst case.

Space Complexity: O(N) for the tree.

Optimal Approach: Recursive with Range

To improve the time complexity, we can use a recursive approach that leverages the properties of preorder traversal and BSTs. We maintain a range (lower bound, upper bound) for each node to ensure that the values are correctly placed.

Algorithm:

1. Define a recursive function that takes the preorder array, an index i (passed by reference), a lower bound, and an upper bound.
2. If the current index i is out of bounds or the current value in preorder is not within the range (lower bound, upper bound), return null.
3. Create a new node with the current value from preorder at index i and increment i.
4. Recursively build the left subtree, updating the upper bound to the current node's value.
5. Recursively build the right subtree, updating the lower bound to the current node's value.
6. Return the created node.

Code (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 {
    int preIndex = 0;

    public TreeNode bstFromPreorder(int[] preorder) {
        return bstFromPreorderRecursive(preorder, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }

    private TreeNode bstFromPreorderRecursive(int[] preorder, int upper, int lower) {
        if (preIndex >= preorder.length) {
            return null;
        }

        int val = preorder[preIndex];
        if (val > upper || val < lower) {
            return null;
        }

        TreeNode node = new TreeNode(val);
        preIndex++;

        node.left = bstFromPreorderRecursive(preorder, val, lower);
        node.right = bstFromPreorderRecursive(preorder, upper, val);

        return node;
    }
}

Time Complexity: O(N), where N is the number of nodes. Each node is visited once.

Space Complexity: O(N) for the recursion stack in the worst case (skewed tree).

Edge Cases

1. Empty preorder array: Should return null.
2. Single element preorder array: Should return a BST with a single node.
3. preorder array with elements that violate BST properties: The problem statement guarantees that such cases will not occur.