BST Iterator Design in DSA C - Build from Scratch

BST Iterator Design

📖 Scenario: Imagine you have a collection of numbers stored in a special tree called a Binary Search Tree (BST). You want to look at these numbers one by one in order, like flipping through pages in a book.

🎯 Goal: You will build a simple program in C that creates a BST, sets up an iterator to go through the tree in order, and prints each number step by step.

📋 What You'll Learn

Create a BST with exact nodes and values

Set up a stack to help with the iterator

Implement functions to initialize the iterator and get the next value

Print the BST values in ascending order using the iterator

💡 Why This Matters

🌍 Real World

BST iterators are used in databases and search engines to efficiently access sorted data without loading everything at once.

💼 Career

Understanding BST iterators helps in roles involving data structure optimization, system design, and coding interviews.

1

Create the BST nodes

Create a struct called TreeNode with int val, TreeNode* left, and TreeNode* right. Then create three nodes named root, node1, and node2 with values 10, 5, and 15 respectively. Connect node1 as the left child and node2 as the right child of root.

DSA C

// Define TreeNode struct and create root, node1, node2 with values 10, 5, 15
// Connect node1 as left child and node2 as right child of root

Hint

Remember to set left and right pointers to NULL for leaf nodes.

2

Set up the stack for the iterator

Create a struct called BSTIterator with an array of TreeNode* named stack of size 10 and an integer top to track the stack's top index. Initialize a variable iterator of type BSTIterator with top set to -1.

DSA C

#include 
#include 

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

typedef struct BSTIterator {
    TreeNode* stack[10];
    int top;
} BSTIterator;

int main() {
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));

    root->val = 10;
    root->left = node1;
    root->right = node2;

    node1->val = 5;
    node1->left = NULL;
    node1->right = NULL;

    node2->val = 15;
    node2->left = NULL;
    node2->right = NULL;

    BSTIterator iterator;
    iterator.top = -1;
    // Your code here
    return 0;
}

Hint

Use an array and an integer to simulate a stack for the iterator.

3

Implement iterator initialization and next function

Write a function void pushLeft(BSTIterator* it, TreeNode* node) that pushes all left children of node onto it->stack. Then write a function int next(BSTIterator* it) that pops the top node from the stack, pushes its right child's left descendants using pushLeft, and returns the popped node's value. In main, call pushLeft(&iterator, root) to initialize.

DSA C

#include 
#include 

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

typedef struct BSTIterator {
    TreeNode* stack[10];
    int top;
} BSTIterator;

void pushLeft(BSTIterator* it, TreeNode* node) {
    // Your code here
}

int next(BSTIterator* it) {
    // Your code here
}

int main() {
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));

    root->val = 10;
    root->left = node1;
    root->right = node2;

    node1->val = 5;
    node1->left = NULL;
    node1->right = NULL;

    node2->val = 15;
    node2->left = NULL;
    node2->right = NULL;

    BSTIterator iterator;
    iterator.top = -1;

    pushLeft(&iterator, root);

    return 0;
}

Hint

Use a loop to push all left nodes. Pop from stack in next and push right child's left nodes.

4

Print BST values using the iterator

In main, use a for loop that runs 3 times. In each loop, call next(&iterator) and print the returned value with printf followed by a space. This will print the BST values in ascending order.

DSA C

#include 
#include 

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

typedef struct BSTIterator {
    TreeNode* stack[10];
    int top;
} BSTIterator;

void pushLeft(BSTIterator* it, TreeNode* node) {
    while (node != NULL) {
        it->stack[++(it->top)] = node;
        node = node->left;
    }
}

int next(BSTIterator* it) {
    TreeNode* node = it->stack[(it->top)--];
    if (node->right != NULL) {
        pushLeft(it, node->right);
    }
    return node->val;
}

int main() {
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node1 = (TreeNode*)malloc(sizeof(TreeNode));
    TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode));

    root->val = 10;
    root->left = node1;
    root->right = node2;

    node1->val = 5;
    node1->left = NULL;
    node1->right = NULL;

    node2->val = 15;
    node2->left = NULL;
    node2->right = NULL;

    BSTIterator iterator;
    iterator.top = -1;

    pushLeft(&iterator, root);

    for (int i = 0; i < 3; i++) {
        // Print next value
    }

    return 0;
}

Hint

Use a for loop to call next(&iterator) three times and print each value with a space.

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