LeetCode 173: Binary Search Tree Iterator Solution in Python Explained

Implementing an iterator for a binary search tree (BST) might feel like designing a tool to stroll through a sorted forest, and LeetCode 173: Binary Search Tree Iterator is a medium-level challenge that makes it engaging! You need to implement a BSTIterator class that iterates over a BST in ascending order (inorder traversal) with two methods: next() to return the next smallest element, and hasNext() to check if there’s a next element. In this blog, we’ll solve it with Python, exploring two solutions—Inorder Traversal with Stack (our best solution) and Flattening to Array (a practical alternative). With step-by-step examples, detailed code breakdowns, and tips, you’ll master this problem. Let’s traverse that tree!

Problem Statement

In LeetCode 173, you’re tasked with implementing a BSTIterator class for a binary search tree:

  • __init__(root): Initializes the iterator with the BST root.
  • next(): Returns the next smallest element (inorder traversal order).
  • hasNext(): Returns true if there’s a next element, false otherwise.

The BST properties ensure inorder traversal yields ascending order, and operations should be efficient (O(1) average time for next and hasNext). This differs from factorial analysis like LeetCode 172: Factorial Trailing Zeroes, focusing on tree iteration rather than number computation.

Constraints

  • Number of nodes: 1 <= n <= 10^5
  • Node values: -2^31 <= val <= 2^31 - 1
  • At most 10^5 calls to next and hasNext
  • next and hasNext should average O(1) time, O(h) space (h = tree height)

Example

Let’s see a case:

Input:
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7,3,15,null,null,9,20]], [], [], [], [], [], [], [], [], []]
Output:
[null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation:
      7
     / \
    3  15
      /  \
     9   20
<ul>
<li>BSTIterator([7,3,15,null,null,9,20]): Initialize.</li>
<li>next(): 3</li>
<li>next(): 7</li>
<li>hasNext(): true</li>
<li>next(): 9</li>
<li>hasNext(): true</li>
<li>next(): 15</li>
<li>hasNext(): true</li>
<li>next(): 20</li>
<li>hasNext(): false</li>
</ul>

This shows inorder iteration over a BST.

Understanding the Problem

How do you solve LeetCode 173: Binary Search Tree Iterator in Python? We need a class to:

  • Initialize with a BST root.
  • Return the next smallest element with next().
  • Check for more elements with hasNext().

For a BST like [7,3,15,null,null,9,20], inorder traversal is [3,7,9,15,20]. We need O(1) average time for operations, suggesting an iterative approach with a stack rather than full traversal upfront. This isn’t a two-sum design like LeetCode 170: Two Sum III - Data Structure Design; it’s about BST iteration. We’ll use: 1. Inorder Traversal with Stack: O(1) average time, O(h) space—our best solution. 2. Flattening to Array: O(n) init, O(1) next/hasNext, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Inorder Traversal with Stack Approach

Explanation

Inorder Traversal with Stack uses a stack to simulate inorder traversal incrementally:

  • __init__: Push all left nodes from root to stack (leftmost path).
  • next(): Pop the top node (smallest), push its right child’s leftmost path, return value.
  • hasNext(): Check if stack is non-empty.

This achieves O(h) time for __init__ (h = height), O(1) average time for next and hasNext (amortized over n calls), and O(h) space (stack holds at most h nodes), making it efficient and space-optimal for BST iteration.

For [7,3,15,null,null,9,20]:

  • Stack: [7,3], pop 3, push 7, pop 7, push 15,9, etc.
  • Sequence: 3, 7, 9, 15, 20.

Step-by-Step Example

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

Example: ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"], [[7,3,15,null,null,9,20]], [], [], [], [], [], [], [], [], []]

Goal: Return [null, 3, 7, true, 9, true, 15, true, 20, false].

  • Step 1: __init__([7,3,15,null,null,9,20]).
    • stack = [], push 7, push 3, stack = [7,3].
  • Step 2: next().
    • Pop 3, node = 3, no right, stack = [7], return 3.
  • Step 3: next().
    • Pop 7, node = 7, push 15, push 9, stack = [15,9], return 7.
  • Step 4: hasNext().
    • stack = [15,9], return true.
  • Step 5: next().
    • Pop 9, stack = [15], return 9.
  • Step 6: hasNext().
    • stack = [15], return true.
  • Step 7: next().
    • Pop 15, push 20, stack = [20], return 15.
  • Step 8: hasNext().
    • stack = [20], return true.
  • Step 9: next().
    • Pop 20, stack = [], return 20.
  • Step 10: hasNext().
    • stack = [], return false.
  • Finish: Output [null, 3, 7, true, 9, true, 15, true, 20, false].

How the Code Works (Inorder Traversal with Stack) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

class BSTIterator:
    def __init__(self, root: TreeNode):
        # Line 1: Initialize stack
        self.stack = []
        # Stack for nodes (e.g., [])

        # Line 2: Push leftmost path
        while root:
            # Traverse left (e.g., 7→3)
            self.stack.append(root)
            # Add node (e.g., [7,3])
            root = root.left
            # Move left (e.g., 3→null)

    def next(self) -> int:
        # Line 3: Pop next smallest node
        node = self.stack.pop()
        # Get smallest (e.g., 3 from [7,3])

        # Line 4: Push right child’s leftmost path
        curr = node.right
        # Move to right (e.g., null, later 15)
        while curr:
            # Traverse left (e.g., 15→9)
            self.stack.append(curr)
            # Add node (e.g., [15,9])
            curr = curr.left
            # Move left (e.g., 9→null)

        # Line 5: Return node value
        return node.val
        # e.g., 3

    def hasNext(self) -> bool:
        # Line 6: Check if more elements
        return len(self.stack) > 0
        # Stack non-empty (e.g., true if [7])

This detailed breakdown clarifies how the stack-based inorder traversal efficiently iterates the BST.

Alternative: Flattening to Array Approach

Explanation

Flattening to Array precomputes the inorder traversal into an array:

  • __init__: Traverse BST inorder, store values in a list.
  • next(): Return next element from list, increment pointer.
  • hasNext(): Check if pointer < list length.

It’s a practical alternative, O(n) time for __init__, O(1) for next and hasNext, but O(n) space (n = nodes), less space-efficient than the stack approach.

For [7,3,15,null,null,9,20]:

  • Array: [3,7,9,15,20], pointer iterates.

Step-by-Step Example (Alternative)

For the same example:

  • __init__: array = [3,7,9,15,20], pointer = 0.
  • next(): array[0] = 3, pointer = 1.
  • next(): array[1] = 7, pointer = 2.
  • hasNext(): 2 < 5, true.
  • Continue: 9, 15, 20, then false.

How the Code Works (Flattening)

class BSTIteratorArray:
    def __init__(self, root: TreeNode):
        self.array = []
        def inorder(node):
            if node:
                inorder(node.left)
                self.array.append(node.val)
                inorder(node.right)
        inorder(root)
        self.pointer = 0

    def next(self) -> int:
        val = self.array[self.pointer]
        self.pointer += 1
        return val

    def hasNext(self) -> bool:
        return self.pointer < len(self.array)

Complexity

  • Inorder Traversal with Stack:
    • Init Time: O(h) – leftmost path.
    • Next Time: O(1) average – amortized over n calls.
    • HasNext Time: O(1) – stack check.
    • Space: O(h) – stack size.
  • Flattening to Array:
    • Init Time: O(n) – full traversal.
    • Next Time: O(1) – array access.
    • HasNext Time: O(1) – pointer check.
    • Space: O(n) – array size.

Efficiency Notes

Inorder Traversal with Stack is the best solution with O(1) average time for next and hasNext, O(h) space (h ≤ n), offering efficiency and space savings—Flattening to Array uses O(n) space and O(n) init time, making it simpler but less space-efficient.

Key Insights

  • Stack: Incremental inorder.
  • Array: Precomputed traversal.
  • BST: Sorted order guaranteed.

Additional Example

For [3,1,4,null,2]:

  • Goal: [1,2,3,4].
  • Stack: [3,1], then [3,2], etc., yields 1,2,3,4.

Edge Cases

  • Single Node: [1] → [1].
  • Left Skew: [3,2,1] → [1,2,3].
  • Right Skew: [1,2,3] → [1,2,3].

Both solutions handle these well.

Final Thoughts

LeetCode 173: Binary Search Tree Iterator in Python is a practical iteration challenge. The Inorder Traversal with Stack solution excels with its efficiency and minimal space, while Flattening to Array offers a straightforward approach. Want more? Try LeetCode 94: Binary Tree Inorder Traversal for basic traversal or LeetCode 167: Two Sum II for pair finding. Ready to practice? Solve LeetCode 173 on LeetCode with [7,3,15,null,null,9,20], aiming for [3,7,9,15,20]—test your skills now!