LeetCode 536: Construct BST from Preorder Traversal Solution in Python – A Step-by-Step Guide

What Is LeetCode 536: Construct BST from Preorder Traversal?

In LeetCode 536: Construct BST from Preorder Traversal, you’re given an array preorder representing the preorder traversal (root, left, right) of a Binary Search Tree (BST), and your task is to return the root of the constructed BST. A BST ensures that for any node, all left subtree values are less than the node’s value, and all right subtree values are greater. For example, with preorder = [8, 5, 1, 7, 10, 12], you build a BST where 8 is the root, 5 leads the left subtree, and 10 leads the right. This problem builds on LeetCode 1008: Construct BST from Preorder Traversal.

Problem Statement

• Input: preorder (List[int])—preorder traversal of a BST.
• Output: TreeNode—root of the constructed BST.
• Rules: BST properties must hold; all values are unique.

Constraints

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10⁸
• All values in preorder are unique.

Examples

• Input: preorder = [8,5,1,7,10,12]
• Output: [8,5,10,1,7,null,12]
• Tree:
``` 8 / \ 5 10 / \ \ 1 7 12 ```
• Input: preorder = [5,3,8]
• Output: [5,3,8]
• Tree:
``` 5 / \ 3 8 ```
• Input: preorder = [1]
• Output: [1]
• Single node tree.

Understanding the Problem: Building a BST

To solve LeetCode 536: Construct BST from Preorder Traversal in Python, we need to reconstruct a BST from its preorder traversal, where the first element is the root, followed by the left subtree, then the right. Since it’s a BST, values less than the root go left, and greater values go right, but identifying subtree boundaries is key. A naive approach might insert each value into a BST iteratively, but we can optimize using preorder properties. We’ll explore:

• Best Solution (Recursive Insertion with Bounds): O(n) time, O(h) space (h = height)—efficient and elegant.
• Alternative Solution (Stack-Based Iterative Approach): O(n) time, O(h) space—clever but trickier.

Let’s dive into the recursive solution with a friendly breakdown!

Best Solution: Recursive Insertion with Bounds

Why Recursive Insertion Wins

The recursive insertion with bounds is the best for LeetCode 536 because it leverages the BST property and preorder traversal order to build the tree in O(n) time with O(h) space (recursion stack), avoiding extra data structures. It uses bounds to determine subtree ranges, making it intuitive and efficient. It’s like planting a tree node-by-node, guided by size limits!

How It Works

Think of this as a tree-growing guide:

• Step 1: Use Bounds:
• Track min and max values for current subtree (e.g., root has no bounds).
• Step 2: Recursive Construction:
• Take next preorder value as root.
• Recurse left if next value < root (within min, root).
• Recurse right if next value > root (within root, max).
• Step 3: Track Index:
• Use a global index to process preorder array sequentially.
• Why It Works:
• Preorder gives root first, then left, then right.
• Bounds ensure BST properties.

It’s like a BST builder’s blueprint!

Step-by-Step Example

Example: preorder = [8, 5, 1, 7, 10, 12]

• Init: index = 0, min_val = float('-inf'), max_val = float('inf').
• Step 1: Root (index=0):
• 8, root = TreeNode(8), index = 1.
• Step 2: Left (min=-inf, max=8):
• 5 < 8, root.left = TreeNode(5), index = 2.
• Left (min=-inf, max=5):
• 1 < 5, root.left.left = TreeNode(1), index = 3.
• Left (min=-inf, max=1): 7 > 1, stop.
• Right (min=5, max=8):
• 7 > 5, root.left.right = TreeNode(7), index = 4.
• Step 3: Right (min=8, max=inf):
• 10 > 8, root.right = TreeNode(10), index = 5.
• Right (min=10, max=inf):
• 12 > 10, root.right.right = TreeNode(12), index = 6.
• Result: Tree matches preorder.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

class Solution:
    def __init__(self):
        self.index = 0

    def constructBST(self, preorder: List[int]) -> TreeNode:
        self.index = 0  # Reset index for each call
        return self.build(preorder, float('-inf'), float('inf'))

    def build(self, preorder: List[int], min_val: float, max_val: float) -> TreeNode:
        # Step 1: Base case - no more elements or out of bounds
        if self.index >= len(preorder) or preorder[self.index] <= min_val or preorder[self.index] >= max_val:
            return None

        # Step 2: Create root node
        root = TreeNode(preorder[self.index])
        self.index += 1

        # Step 3: Recursively build left and right subtrees
        root.left = self.build(preorder, min_val, root.val)
        root.right = self.build(preorder, root.val, max_val)

        return root

• Line 8: Index as instance variable for recursion.
• Line 12: Start with full range.
• Lines 15-17: Stop if index out of bounds or value violates BST range.
• Lines 20-21: Create root, increment index.
• Lines 24-25: Recurse left (less than root), right (greater than root).
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a BST construction maestro!

Alternative Solution: Stack-Based Iterative Approach

Why an Alternative Approach?

The stack-based iterative approach uses a stack to track nodes and build the BST in O(n) time and O(h) space, avoiding recursion. It’s clever but less intuitive, requiring careful stack management. Great for iterative enthusiasts!

How It Works

Picture this as a BST stack builder:

• Step 1: Start with root, push to stack.
• Step 2: Iterate preorder:
• If next value < top, add as left child, push.
• If next value > top, pop until valid, add as right child.
• Step 3: Build tree iteratively.

It’s like a BST stack assembler!

Step-by-Step Example

Example: preorder = [8, 5, 1, 7, 10, 12]

• Init: stack = [], root = TreeNode(8), push 8.
• Step 1: 5 < 8, 8.left = 5, push 5, stack = [8, 5].
• Step 2: 1 < 5, 5.left = 1, push 1, stack = [8, 5, 1].
• Step 3: 7 > 1, pop 1, 7 > 5, pop 5, 7 < 8, 5.right = 7, push 7, stack = [8, 7].
• Step 4: 10 > 7, pop 7, 10 > 8, pop 8, 8.right = 10, push 10, stack = [10].
• Step 5: 12 > 10, 10.right = 12, push 12, stack = [10, 12].
• Result: Same BST.

Code for Stack Approach

Copy codeclass Solution:
    def constructBST(self, preorder: List[int]) -> TreeNode:
        if not preorder:
            return None

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

        for i in range(1, len(preorder)):
            node = TreeNode(preorder[i])
            if preorder[i] < stack[-1].val:
                stack[-1].left = node
            else:
                last_popped = None
                while stack and preorder[i] > stack[-1].val:
                    last_popped = stack.pop()
                last_popped.right = node
            stack.append(node)

        return root

• Lines 6-7: Start with root, initialize stack.
• Lines 9-17: For each value, add as left or right, manage stack.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(h)—stack size.

It’s a stack-based BST maker!

Comparing the Two Solutions

• Recursive (Best):
• Pros: O(n), O(h), intuitive.
• Cons: Recursion stack.
• Stack Iterative (Alternative):
• Pros: O(n), O(h), iterative.
• Cons: Stack logic.

Recursive wins for clarity!

Additional Examples and Edge Cases

• [1]: Single node.
• [5, 3]: Root 5, left 3.
• [10, 5, 15, 3, 7]: Full BST.

Recursive handles them all!

Complexity Recap

• Recursive: Time O(n), Space O(h).
• Stack: Time O(n), Space O(h).

Recursive’s the elegance champ!

Key Takeaways

• Recursive: Bounds guide—learn at Python Basics!
• Stack: Iterative twist.
• Trees: BSTs are fun.
• Python: Recursion or stacks, your pick!

Final Thoughts: Build That BST!

LeetCode 536: Construct BST from Preorder Traversal in Python is a delightful tree challenge. Recursive insertion with bounds is your fast track, while stack-based iteration offers a clever alternative. Want more? Try LeetCode 1008: Construct BST from Preorder or LeetCode 94: Inorder Traversal. Ready to construct? Head to Solve LeetCode 536 on LeetCode and build that BST today!