NUHMAN.com

Introduction

LeetCode 173 asks you to implement an iterator for a Binary Search Tree (BST). The iterator should return the next smallest number in the BST, as if it were performing an in-order traversal (left, root, right).

The iterator should support the following operations:

• next(): Returns the next smallest number in the BST.
• hasNext(): Returns true if there is a next smallest number in the BST, otherwise returns false.

This problem is an example of a common pattern where you need to implement an iterator for a tree structure, and it can be efficiently solved using a stack for an in-order traversal.

Problem Statement

Design an iterator over a binary search tree (BST) where the elements are visited in ascending order.

Implement the BSTIterator class:

go

type BSTIterator struct {
    stack []*TreeNode
}

Constructor:

• Constructor(root *TreeNode) Initializes the iterator with the root of the binary search tree.

Methods:

• next() Returns the next smallest number in the BST.
• hasNext() Returns true if there is a next smallest number, otherwise false.

TreeNode Definition:

go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

Approach

In-Order Traversal using Stack:

We can leverage the stack to simulate an in-order traversal of the BST:

1. In-order Traversal: In an in-order traversal, we first visit all the left children of the current node, then visit the node itself, and finally visit the right children.
2. Using Stack:

• We can push all the left nodes of the current node into the stack.
• When calling next(), we pop an element from the stack (the smallest unvisited node), then push its right child and its descendants into the stack.

1. Efficiency:

• The next() function will return the next smallest number by popping from the stack. The hasNext() function will check if there are any elements left in the stack.

Time Complexity:

• next() operation: O(1), as it involves popping from the stack.
• hasNext() operation: O(1), as it just checks the stack.

Space Complexity:

• O(h), where h is the height of the tree. This is because, in the worst case, we store the nodes along the path to the leftmost node.

Go Implementation

go

type BSTIterator struct {
    stack []*TreeNode
}

// Constructor initializes the BSTIterator with the root of the BST.
func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{}
    iterator.pushLeft(root)
    return iterator
}

// pushLeft pushes all the left children of the given node onto the stack.
func (this *BSTIterator) pushLeft(node *TreeNode) {
    for node != nil {
        this.stack = append(this.stack, node)
        node = node.Left
    }
}

// next returns the next smallest number in the BST.
func (this *BSTIterator) next() int {
    // The top of the stack is the next smallest element.
    top := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    
    // If the current node has a right child, push all its left children to the stack.
    if top.Right != nil {
        this.pushLeft(top.Right)
    }

    return top.Val
}

// hasNext returns true if there is a next smallest number, otherwise false.
func (this *BSTIterator) hasNext() bool {
    return len(this.stack) > 0
}

Explanation of the Code:

1. Constructor:

• The Constructor initializes the iterator with the root of the binary search tree. It calls the pushLeft() function to push all the left children of the root into the stack.

1. pushLeft():

• This function takes a node and pushes all its left children onto the stack, simulating the in-order traversal's leftward path.

1. next():

• This function pops the top element from the stack (the next smallest element in the in-order traversal).
• If the popped node has a right child, the right child and its left descendants are pushed onto the stack.

1. hasNext():

• This function checks if there are any nodes left in the stack. If the stack is non-empty, it returns true indicating that there are more elements to iterate through. If the stack is empty, it returns false.

Example

Example 1:

go

root := &TreeNode{Val: 7}
root.Left = &TreeNode{Val: 3}
root.Right = &TreeNode{Val: 15}
root.Right.Left = &TreeNode{Val: 9}
root.Right.Right = &TreeNode{Val: 20}

iterator := Constructor(root)

fmt.Println(iterator.next())    // Output: 3
fmt.Println(iterator.next())    // Output: 7
fmt.Println(iterator.hasNext()) // Output: true
fmt.Println(iterator.next())    // Output: 9
fmt.Println(iterator.hasNext()) // Output: true
fmt.Println(iterator.next())    // Output: 15
fmt.Println(iterator.hasNext()) // Output: true
fmt.Println(iterator.next())    // Output: 20
fmt.Println(iterator.hasNext()) // Output: false

Explanation:

1. The BST is constructed as follows:

markdown

    7
   / \
  3   15
     /  \
    9    20

1. The iterator iterates through the tree in in-order:

• First, it returns 3, then 7, then 9, then 15, and finally 20.
• After the final next(), the hasNext() function will return false since all elements have been visited.

Conclusion

LeetCode 173: Binary Search Tree Iterator can be efficiently solved using an in-order traversal and a stack to simulate the process. By leveraging the stack to store the left path and ensuring we pop and push the right subtree correctly, we can achieve constant-time complexity for both next() and hasNext().