Why BST Iterator Design in DSA Go?

The Big Idea

Discover how a simple iterator can turn a confusing tree into a smooth, step-by-step journey!

The Scenario

Imagine you have a large family tree drawn on paper, and you want to look at each member one by one in order from youngest to oldest. Doing this manually means flipping back and forth through the pages, trying to remember where you left off.

The Problem

Manually tracking where you are in the family tree is slow and confusing. You might lose your place, repeat members, or skip some. It's hard to keep the order right without a clear system.

The Solution

A BST Iterator acts like a smart bookmark that remembers exactly where you are in the tree. It lets you move step-by-step in order, without losing track or needing to start over.

Before vs After

✗ Before

func inorderTraversal(root *TreeNode) []int {
    var result []int
    var stack []*TreeNode
    current := root
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, current.Val)
        current = current.Right
    }
    return result
}

✓ After

type BSTIterator struct {
    stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{stack: []*TreeNode{}}
    iterator.pushLeft(root)
    return iterator
}

func (it *BSTIterator) pushLeft(node *TreeNode) {
    for node != nil {
        it.stack = append(it.stack, node)
        node = node.Left
    }
}

func (it *BSTIterator) Next() int {
    node := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]
    it.pushLeft(node.Right)
    return node.Val
}

func (it *BSTIterator) HasNext() bool {
    return len(it.stack) > 0
}

What It Enables

This design lets you explore a binary search tree step-by-step in order, efficiently and without extra memory for the whole tree.

Real Life Example

Think of browsing a sorted list of contacts on your phone. The BST Iterator helps you move from one contact to the next in alphabetical order without loading all contacts at once.

Key Takeaways

Manual tree traversal is hard to pause and resume.

BST Iterator remembers your place and moves in order.

It uses a stack to track nodes efficiently.