0173.Binary Search Tree Iterator

Link: 173. Binary Search Tree Iterator - Medium

Question

Restate the problem

Given the root of BST
We need to implement an iterator class over a BST

• next(), returns the next smallest number each time.
• hasNext(), return where more nodes exist

Inorder: left → node → right

---

Method 1 stack - optimal
Method 2 DFS - extra memory

Method1 - Traversal with Stack

Approach

Use stack to simulate the recursion and a point cur to traverse

• Repeatedly go left: While cur is not null, keep going left and push each node onto stack
• When cur is null, pop a node from stack, add node.val to result, then set cur = node.right to process its right subtree
• Stop when both null and stack is empty

Complexity

• Time Complexity: O(n)
• Space Complexity: O(h)

Edge Case

• No root

Code

class BSTIterator:
 
    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.cur = root
 
    def next(self) -> int:
        while self.stack or self.cur:
            while self.cur:
                self.stack.append(self.cur)
                self.cur = self.cur.left
            
            node = self.stack.pop()
            res = node.val
            self.cur = node.right
            return res
 
    def hasNext(self) -> bool:
        return True if self.stack or self.cur else False

Method2 - DFS

Code

class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.arr = []
        self.idx = 0
        
        def dfs(node):
            if not node:
                return None
            
            dfs(node.left)
            self.arr.append(node.val)
            dfs(node.right)
        
        dfs(root)
 
    def next(self) -> int:
        val = self.arr[self.idx]
        self.idx += 1
        return val
 
    def hasNext(self) -> bool:
        return self.idx < len(self.arr)

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

---

History

Jan-19-2026 Solved dfs method, Hinted stack method