We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct Binary Search Tree from Preorder Traversal

Number: 1050

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Microsoft, Google, Bloomberg

Problem Description

Given an array of integers representing the preorder traversal of a binary search tree (BST), construct the BST and return its root. Recall that in a BST, for every node, all nodes in the left subtree have values strictly less than the node’s value and all nodes in the right subtree have values strictly greater. The preorder traversal visits nodes in the order: root, left subtree, then right subtree.

Key Insights

  • The preorder sequence always starts with the root of the tree.
  • For any node, elements in the left subtree must be less than the node’s value, while elements in the right subtree must be greater.
  • Use recursion with bounds (or an iterative approach with a stack) to determine where a new value fits in the BST.
  • Maintain an index into the preorder array to build the tree sequentially.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes since each node is processed exactly once. Space Complexity: O(n) in the worst case due to the recursion call stack (for a skewed tree).

Solution

We can solve this problem using a recursive approach. The recursive function will have lower and upper bounds which restrict the valid range for node values at each stage. Starting with the entire range (-∞, +∞), we process each value in the preorder list in order. If the next value lies within the bounds, it is accepted as a node. We then recursively construct the left subtree with an updated upper bound (current node's value) and the right subtree with an updated lower bound (current node's value). This ensures that the BST property is maintained throughout.

The key data structure used is the recursion call stack, which inherently manages the bounds for a valid BST construction. The algorithm processes each element of the preorder sequence exactly once, leading to optimal time complexity.

Code Solutions

# 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

# Recursive helper function that utilizes bounds to construct the BST.
def bstFromPreorder(preorder):
    # use a list to simulate a pointer that holds the current index reference
    index = [0]
    
    # Recursive function to build BST within the lower and upper bounds
    def buildBST(lower, upper):
        # If all elements are used, return None.
        if index[0] == len(preorder):
            return None
        # next value in the preorder sequence
        val = preorder[index[0]]
        # If the value does not satisfy BST constraints, return None.
        if val < lower or val > upper:
            return None
        
        # Accept the value and move to the next element
        index[0] += 1
        # Create a new tree node with the current value.
        node = TreeNode(val)
        # All values for the left subtree must be less than the current node's value.
        node.left = buildBST(lower, val)
        # All values for the right subtree must be greater than the current node's value.
        node.right = buildBST(val, upper)
        return node
    
    return buildBST(float('-inf'), float('inf'))

# Example usage:
# preorder = [8,5,1,7,10,12]
# root = bstFromPreorder(preorder)
← Back to All Questions