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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct Binary Search Tree from Preorder Traversal

Difficulty: Medium

Problem Description

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.

Key Insights

  • A preorder traversal visits nodes in the order: root, left subtree, right subtree.
  • The first element in the preorder array is always the root of the tree.
  • All subsequent elements can be divided into left and right subtrees based on their values relative to the root.
  • The left subtree contains values less than the root, while the right subtree contains values greater than the root.

Space and Time Complexity

Time Complexity: O(n) - Each node is processed once. Space Complexity: O(n) - Space used by the recursive call stack and the tree itself.

Solution

To construct the binary search tree (BST) from the preorder traversal, we can utilize a recursive approach. The first element of the preorder array serves as the root of the BST. We then iterate through the array to find elements that belong to the left and right subtrees based on the value of the root. We create a new tree node for each element and recursively build the left and right subtrees. This process continues until all elements from the array are processed.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def bstFromPreorder(preorder):
    if not preorder:
        return None

    root = TreeNode(preorder[0])  # Create the root node
    stack = [root]  # Initialize stack with root
    for value in preorder[1:]:  # Iterate over the rest of the values
        node = TreeNode(value)  # Create a new node for the value
        if value < stack[-1].val:  # If the value is less than the last node in stack
            stack[-1].left = node  # Assign it to the left
        else:
            # Find the parent to which this node should be assigned
            while stack and stack[-1].val < value:
                last = stack.pop()  # Pop the last element until we find the correct parent
            last.right = node  # Assign to the right of the parent
        stack.append(node)  # Push the new node onto the stack
    return root
← Back to All Questions