Binary Search Tree Iterator

LeetCode 173 | Difficulty: Medium

Medium

Problem Description

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

- `BSTIterator(TreeNode root)` Initializes an object of the `BSTIterator` class. The `root` of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.

- `boolean hasNext()` Returns `true` if there exists a number in the traversal to the right of the pointer, otherwise returns `false`.

- `int next()` Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

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
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

Constraints:

- The number of nodes in the tree is in the range `[1, 10^5]`.

- `0 <= Node.val <= 10^6`

- At most `10^5` calls will be made to `hasNext`, and `next`.

Follow up:

- Could you implement `next()` and `hasNext()` to run in average `O(1)` time and use `O(h)` memory, where `h` is the height of the tree?

Topics: Stack, Tree, Design, Binary Search Tree, Binary Tree, Iterator

---

Approach

Stack

Use a stack (LIFO) to track elements that need future processing. Process elements when a "trigger" condition is met (e.g., finding a smaller/larger element). Monotonic stack maintains elements in sorted order for next greater/smaller element problems.

When to use

Matching brackets, next greater element, evaluating expressions, backtracking history.

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

---

Solutions

Solution 1: C# (Best: 152 ms)

Metric	Value
Runtime	152 ms
Memory	50.5 MB
Date	2022-01-04

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class BSTIterator
{
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    public BSTIterator(TreeNode root)
    {
        PushAll(root);
    }

    public int Next()
    {
        TreeNode temp = stack.Pop();
        PushAll(temp.right);
        return temp.val;
    }

    public bool HasNext()
    {
        return stack.Any();
    }
    
    private void PushAll(TreeNode node)
    {
        while(node != null)
        {
            stack.Push(node);
            node = node.left;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */

📜 1 more C# submission(s)

Submission (2022-01-04) — 221 ms, 48.9 MB

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class BSTIterator
{
    private TreeNode cur;
    public BSTIterator(TreeNode root)
    {
        cur = root;
    }

    public bool HasNext()
    {
        return cur != null;
    }

    public int Next()
    {
        int r = 0;
        while (cur != null)
        {
            if (cur.left == null)
            {
                r = cur.val;
                cur = cur.right;
                // Got the node, break loop
                break;
            }
            else
            {
                TreeNode node = cur.left;
                while (node.right != null && node.right != cur)
                {
                    node = node.right;
                }
                if (node.right == null)
                {
                    node.right = cur;
                    cur = cur.left;
                }
                else
                {
                    node.right = null;
                    r = cur.val;
                    cur = cur.right;
                    // Got the node, break loop
                    break;
                }
            }
        }
        return r;
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.Next();
 * bool param_2 = obj.HasNext();
 */

---

Complexity Analysis

Approach	Time	Space
Stack	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.
• Think about what triggers a pop: is it finding a match, or finding a smaller/larger element?
• Clarify the expected time complexity for each operation before choosing data structures.