How do you solve Binary Search Tree Iterator on LeetCode?

Binary Search Tree Iterator (LeetCode #173) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Using a stack allows for efficient in-order traversal without extra space for all elements.

What is the brute force solution for Binary Search Tree Iterator?

The brute force approach for Binary Search Tree Iterator is Brute Force, with O(n²) time complexity and O(n) space complexity. The simplest way to implement the BST iterator is to perform an in-order traversal of the tree and store the elements in a list. This allows us to access elements in order but requires extra space and time. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Binary Search Tree Iterator?

Explain your thought process clearly as you write code. Discuss the trade-offs of different approaches. Practice writing code without an IDE to simulate interview conditions.

What are common mistakes when solving Binary Search Tree Iterator?

Not understanding how in-order traversal works in a BST. Confusing the stack operations and their order.

#173

Binary Search Tree Iterator

Medium

StackTreeDesignBinary Search TreeBinary TreeIteratorStackTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(h)

💡

Intuition

Time O(n)Space O(h)

Instead of storing all elements in a list, we can use a stack to keep track of nodes. This allows us to perform the in-order traversal on-the-fly, which saves space and keeps the time complexity efficient.

⚙️

Algorithm

3 steps

1Step 1: Initialize a stack to store nodes and push all left children of the root onto the stack.
2Step 2: In the next() method, pop the top node from the stack, push its right child (if exists) and all its left children onto the stack.
3Step 3: The hasNext() method checks if the stack is not empty.

solution.py18 lines

1# Full working Python code
2class BSTIterator:
3    def __init__(self, root):
4        self.stack = []
5        self._push_left(root)
6
7    def _push_left(self, node):
8        while node:
9            self.stack.append(node)
10            node = node.left
11
12    def next(self):
13        node = self.stack.pop()
14        self._push_left(node.right)
15        return node.val
16
17    def hasNext(self):
18        return len(self.stack) > 0

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(h) where h is the height of the tree, due to the stack storing nodes along the path from the root to the current node.

1Using a stack allows for efficient in-order traversal without extra space for all elements.
2The iterator design pattern is useful for sequential access to elements.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.