LeetCode 1008: Construct Binary Search Tree from Preorder Traversal Solution

Master LeetCode problem 1008 (Construct Binary Search Tree from Preorder Traversal), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1008. Construct Binary Search Tree from Preorder Traversal

Medium

Array Stack Tree Binary Search Tree Monotonic Stack Binary Tree

Problem Explanation

Explanation

To construct a binary search tree from the given preorder traversal array, we can use a recursive approach. We start by taking the first element from the preorder array as the root of the BST. Then, we iterate through the remaining elements in the array to find the right place to insert them based on the binary search tree property.

For each element in the preorder array, we recursively build the left and right subtrees based on whether the element is less than or greater than the current node's value. By keeping track of the range of valid values for each subtree, we can efficiently construct the binary search tree.

Time Complexity

The time complexity of this approach is O(n) where n is the number of elements in the preorder array.

Space Complexity

The space complexity is O(n) for the recursive call stack.

Solution Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        return bstFromPreorder(preorder, 0, preorder.length - 1);
    }
    
    private TreeNode bstFromPreorder(int[] preorder, int start, int end) {
        if (start > end) {
            return null;
        }
        
        TreeNode root = new TreeNode(preorder[start]);
        int rightIdx = start + 1;
        
        while (rightIdx <= end && preorder[rightIdx] < preorder[start]) {
            rightIdx++;
        }
        
        root.left = bstFromPreorder(preorder, start + 1, rightIdx - 1);
        root.right = bstFromPreorder(preorder, rightIdx, end);
        
        return root;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1008 (Construct Binary Search Tree from Preorder Traversal)?

This page provides optimized solutions for LeetCode problem 1008 (Construct Binary Search Tree from Preorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1008 (Construct Binary Search Tree from Preorder Traversal)?

The time complexity for LeetCode 1008 (Construct Binary Search Tree from Preorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1008 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1008 in Java, C++, or Python.

Back to LeetCode Solutions