BST Iterator Design in DSA C

Mental Model

A BST iterator lets you visit nodes in order without storing all nodes at once. It uses a stack to remember where to go next.

Analogy: Imagine reading a book with bookmarks. You keep bookmarks on pages you might return to later, so you don't have to start over each time.

      7
     / \
    3   15
       /  \
      9    20
Stack: []
Current: null

Dry Run Walkthrough

Input: BST with nodes 7, 3, 15, 9, 20; iterate to get next smallest values

Goal: Visit nodes in ascending order: 3, 7, 9, 15, 20

Step 1: Initialize iterator by pushing left path from root (7) to stack

Stack: [7, 3]
Current: null

Why: We start from smallest node by going left as far as possible

Step 2: Pop 3 from stack, return 3, move to right child (null)

Stack: [7]
Current: null

Why: 3 has no left child, so next is 3 itself, then move right which is null

Step 3: Pop 7 from stack, return 7, move to right child (15), push left path

Stack: [15, 9]
Current: null

Why: After 7, next smallest is leftmost of right subtree

Step 4: Pop 9 from stack, return 9, move to right child (null)

Stack: [15]
Current: null

Why: 9 has no left child, so next is 9, then move right which is null

Step 5: Pop 15 from stack, return 15, move to right child (20), push left path

Stack: [20]
Current: null

Why: After 15, next smallest is leftmost of right subtree

Step 6: Pop 20 from stack, return 20, move to right child (null)

Stack: []
Current: null

Why: 20 is last node, no right child

Result:

3 -> 7 -> 9 -> 15 -> 20 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Definition for a binary tree node.
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Stack node for iterator
typedef struct StackNode {
    TreeNode *treeNode;
    struct StackNode *next;
} StackNode;

// Stack operations
void push(StackNode **top, TreeNode *node) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    newNode->treeNode = node;
    newNode->next = *top;
    *top = newNode;
}

TreeNode *pop(StackNode **top) {
    if (*top == NULL) return NULL;
    StackNode *temp = *top;
    TreeNode *res = temp->treeNode;
    *top = temp->next;
    free(temp);
    return res;
}

int isEmpty(StackNode *top) {
    return top == NULL;
}

// BST Iterator structure
typedef struct {
    StackNode *stack;
} BSTIterator;

// Initialize iterator by pushing left path
BSTIterator* bSTIteratorCreate(TreeNode* root) {
    BSTIterator *iter = (BSTIterator *)malloc(sizeof(BSTIterator));
    iter->stack = NULL;
    TreeNode *curr = root;
    while (curr != NULL) {
        push(&iter->stack, curr); // push left nodes
        curr = curr->left;
    }
    return iter;
}

// Returns true if there is a next smallest number
int bSTIteratorHasNext(BSTIterator* obj) {
    return !isEmpty(obj->stack);
}

// Returns next smallest number
int bSTIteratorNext(BSTIterator* obj) {
    TreeNode *node = pop(&obj->stack); // pop top
    int val = node->val;
    TreeNode *curr = node->right; // move to right subtree
    while (curr != NULL) {
        push(&obj->stack, curr); // push left path of right subtree
        curr = curr->left;
    }
    return val;
}

// Helper to create tree nodes
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Construct BST
    TreeNode *root = newNode(7);
    root->left = newNode(3);
    root->right = newNode(15);
    root->right->left = newNode(9);
    root->right->right = newNode(20);

    BSTIterator *iter = bSTIteratorCreate(root);
    while (bSTIteratorHasNext(iter)) {
        int val = bSTIteratorNext(iter);
        printf("%d -> ", val);
    }
    printf("null\n");
    return 0;
}

while (curr != NULL) { push(&iter->stack, curr); curr = curr->left; }

push leftmost nodes to stack to start with smallest

TreeNode *node = pop(&obj->stack); int val = node->val;

pop top node from stack as next smallest

curr = node->right; while (curr != NULL) { push(&obj->stack, curr); curr = curr->left; }

push left path of right subtree to stack for next calls

return val;

return the next smallest value

Output

3 -> 7 -> 9 -> 15 -> 20 -> null

Complexity Analysis

Time: O(1) average per next() call because each node is pushed and popped once

Space: O(h) where h is tree height, due to stack storing left path

vs Alternative: Compared to storing all nodes in a list (O(n) space), this uses less memory and supports on-demand traversal

Edge Cases

Empty tree

Iterator stack is empty, hasNext returns false immediately

DSA C

while (curr != NULL) { push(&iter->stack, curr); curr = curr->left; }

Tree with single node

Stack has one node, next returns that node, then empty

DSA C

while (curr != NULL) { push(&iter->stack, curr); curr = curr->left; }

Right skewed tree

Stack holds one node at a time, iterator moves right each time

DSA C

curr = node->right; while (curr != NULL) { push(&obj->stack, curr); curr = curr->left; }

When to Use This Pattern

When you need to traverse a BST in sorted order without using extra space for all nodes, use BST Iterator pattern with a stack to simulate controlled traversal.

Common Mistakes

Mistake: Pushing all nodes into a list at once instead of using a stack for lazy traversal
Fix: Use a stack to push only left children and push right subtree left paths on demand

Mistake: Not pushing left children of right subtree after popping a node
Fix: After popping a node, push all left children of its right child to stack

Summary

It lets you visit BST nodes in ascending order using a stack to remember where to go next.

Use it when you want sorted traversal of BST without storing all nodes at once.

The key is to push left children on stack and after visiting a node, push left path of its right subtree.

Practice

1. What is the main purpose of a BST Iterator in a binary search tree?

easy

A. To delete nodes from the BST

B. To insert new nodes into the BST

C. To balance the BST automatically

D. To traverse the BST in ascending order without recursion

Solution

1. Step 1: Understand BST Iterator functionality

   A BST Iterator is designed to traverse the tree in sorted order, typically ascending, without using recursion.

2. Step 2: Identify the main purpose

   It provides a way to get the next smallest element efficiently, which matches To traverse the BST in ascending order without recursion.

3. Final Answer:

   To traverse the BST in ascending order without recursion -> Option D

4. Quick Check:

   BST Iterator = In-order traversal without recursion [OK]

Hint: BST Iterator returns next smallest element in sorted order [OK]

Common Mistakes:

• Confusing iterator with insertion or deletion
• Thinking it balances the tree automatically
• Assuming it uses recursion internally

2. Which of the following is the correct way to declare a stack for implementing a BST Iterator in C?

easy

A. int stack[100]; int top = -1;

B. stack<int> s; // C++ syntax

C. List<int> stack = new List<int>();

D. var stack = [];

Solution

1. Step 1: Identify language and syntax

   The question is about C language, so C++ or other language syntax is invalid.

2. Step 2: Choose correct C stack declaration

   int stack[100]; int top = -1; declares a fixed-size integer array and a top index, which is the typical way to implement a stack in C.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   C stack = array + top index [OK]

Hint: Use array and top index for stack in C [OK]

Common Mistakes:

• Using C++ or other language syntax in C
• Using dynamic lists not available in C
• Using var keyword which is not in C

3. Consider the following BST Iterator code snippet in C. What will be the output sequence of next() calls?

typedef struct Node {
  int val;
  struct Node* left;
  struct Node* right;
} Node;

// Assume stack and top are global
void push(Node* node) { stack[++top] = node; }
Node* pop() { return stack[top--]; }

void pushLeft(Node* root) {
  while (root) {
    push(root);
    root = root->left;
  }
}

Node* next() {
  Node* node = pop();
  pushLeft(node->right);
  return node;
}

// BST structure:
//       5
//      / \
//     3   7
//    / \   \
//   2   4   8

// Initial call: pushLeft(root) where root = 5

// Calls: next(), next(), next(), next(), next(), next()

medium

A. [2, 4, 3, 5, 8, 7]

B. [5, 3, 2, 4, 7, 8]

C. [2, 3, 4, 5, 7, 8]

D. [8, 7, 5, 4, 3, 2]

Solution

1. Step 1: Understand pushLeft and next behavior

   pushLeft pushes all left children starting from root. next pops top node, then pushes left children of right subtree.

2. Step 2: Trace calls step-by-step

   Initial stack after pushLeft(5): [5,3,2] (top is 2). next() pops 2 (no right child), output 2.
   next() pops 3, pushes left of 4 (which is 4), output 3.
   next() pops 4 (no right child), output 4.
   next() pops 5, pushes left of 7 (which is 7), output 5.
   next() pops 7, pushes left of 8 (which is 8), output 7.
   next() pops 8, output 8.

3. Final Answer:

   [2, 3, 4, 5, 7, 8] -> Option C

4. Quick Check:

   In-order traversal = [2,3,4,5,7,8] [OK]

Hint: Trace stack push/pop for in-order sequence [OK]

Common Mistakes:

• Ignoring pushLeft on right child
• Assuming preorder or postorder output
• Mixing up stack order

4. The following code snippet for BST Iterator has a bug. What is the error?

typedef struct Node {
  int val;
  struct Node* left;
  struct Node* right;
} Node;

Node* stack[100];
int top = -1;

void push(Node* node) { stack[++top] = node; }
Node* pop() { return stack[top--]; }

void pushLeft(Node* root) {
  while (root != NULL) {
    push(root);
    root = root->left;
  }
}

Node* next() {
  Node* node = pop();
  pushLeft(node->right);
  return node;
}

int hasNext() {
  return top >= 0;
}

// Usage:
// pushLeft(root);
// while (hasNext()) {
//   Node* n = next();
//   printf("%d ", n->val);
// }

medium

A. pop() returns NULL when stack is empty causing crash

B. Stack overflow if BST is large and pushLeft pushes too many nodes

C. pushLeft does not handle NULL root correctly

D. hasNext() returns wrong boolean value

Solution

1. Step 1: Analyze stack usage in pushLeft

   pushLeft pushes all left nodes onto stack. For a very deep BST, this can exceed stack size 100 causing overflow.

2. Step 2: Check other functions for errors

   pop() assumes stack not empty; hasNext() correctly checks top >= 0; pushLeft handles NULL root by stopping loop.

3. Final Answer:

   Stack overflow if BST is large and pushLeft pushes too many nodes -> Option B

4. Quick Check:

   Fixed stack size risks overflow [OK]

Hint: Check fixed stack size limits for large BSTs [OK]

Common Mistakes:

• Assuming pop() returns NULL safely
• Thinking pushLeft fails on NULL root
• Believing hasNext() logic is incorrect

5. You want to design a BST Iterator that supports next() and hasNext() in O(1) average time and uses O(h) memory, where h is tree height. Which approach best achieves this?

hard

A. Use a stack to store left children, pushing right subtree nodes on next() calls

B. Store all nodes in an array by in-order traversal at initialization

C. Use recursion to traverse nodes on each next() call

D. Use a queue to store nodes level by level

Solution

1. Step 1: Understand time and space constraints

   O(1) average time per next() and O(h) memory means no full traversal storage and no recursion per call.

2. Step 2: Evaluate options

   Use a stack to store left children, pushing right subtree nodes on next() calls uses a stack to store left children only, pushing right subtree nodes lazily, matching constraints.
   Store all nodes in an array by in-order traversal at initialization uses O(n) memory, violating O(h).
   Use recursion to traverse nodes on each next() call uses recursion each call, not O(1) average.
   Use a queue to store nodes level by level uses queue level order, not in-order traversal.

3. Final Answer:

   Use a stack to store left children, pushing right subtree nodes on next() calls -> Option A

4. Quick Check:

   Stack + lazy push = O(1) avg time & O(h) space [OK]

Hint: Stack with lazy right pushes fits O(1) avg time and O(h) space [OK]

Common Mistakes:

• Precomputing all nodes wastes memory
• Using recursion each next() call is slow
• Using queue gives wrong traversal order