Binary Search Tree Iterator - Practice Coding Problems

Binary Search Tree Iterator - Problem

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.

Input & Output

Example 1 — Basic BST Iterator

$ Input: commands = ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"], values = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

› Output: [null, 3, 7, true, 9, true, 15, true, 20, false]

💡 Note: Initialize iterator with BST root 7. In-order traversal gives 3,7,9,15,20. Each next() returns the next smallest value, hasNext() checks if more values exist.

Example 2 — Single Node Tree

$ Input: commands = ["BSTIterator", "next", "hasNext"], values = [[[5]], [], []]

› Output: [null, 5, false]

💡 Note: Tree with single node 5. First next() returns 5, then hasNext() returns false as no more values exist.

Example 3 — Left Skewed Tree

$ Input: commands = ["BSTIterator", "next", "next", "hasNext"], values = [[[3, 1, null, null, 2]], [], [], []]

› Output: [null, 1, 2, true]

💡 Note: Left-skewed BST. In-order traversal: 1,2,3. After getting 1 and 2, hasNext() is true because 3 remains.

Constraints

The number of nodes in the tree is in the range [1, 10⁵]
0 ≤ Node.val ≤ 10⁶
At most 10⁵ calls will be made to hasNext, and next

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary search tree [7,3,15,null,null,9,20]

In-order Sequence

Values in sorted order: 3,7,9,15,20

Iterator Operations

next() and hasNext() return values on-demand

Key Takeaway

🎯 Key Insight: Use a stack to simulate recursive traversal, generating sorted values on-demand with minimal memory

Asked in

F Facebook 35 G Google 28 a Amazon 22 M Microsoft 18

The key insight is to use a stack to simulate the call stack of recursive in-order traversal, allowing us to generate values on-demand. The optimal approach uses controlled recursion with a stack, achieving O(1) amortized time per operation and O(h) space where h is tree height. Time: O(n) total, Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Pre-compute All Values	O(n)	O(n)	Store all values in a list during initialization, then iterate through the list
Controlled Recursion with Stack	O(n)	O(h)	Use a stack to simulate in-order traversal and generate values on-demand

Pre-compute All Values — Algorithm Steps

Step 1: Traverse entire BST in-order and store values in array
Step 2: Use index to track current position
Step 3: Return values from array sequentially

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Tree

Binary search tree with values 7,3,15,9,20

In-order Traversal

Visit nodes in sorted order: 3,7,9,15,20

Array Storage

Store values in array and use index pointer

Code -

solution.c — C

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

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

typedef struct {
    int* values;
    int size;
    int index;
} BSTIterator;

void inorder(struct TreeNode* node, int* arr, int* idx) {
    if (node) {
        inorder(node->left, arr, idx);
        arr[(*idx)++] = node->val;
        inorder(node->right, arr, idx);
    }
}

BSTIterator* bSTIteratorCreate(struct TreeNode* root) {
    BSTIterator* obj = (BSTIterator*)malloc(sizeof(BSTIterator));
    obj->values = (int*)malloc(1000 * sizeof(int));
    obj->size = 0;
    obj->index = -1;
    
    inorder(root, obj->values, &(obj->size));
    return obj;
}

int bSTIteratorNext(BSTIterator* obj) {
    obj->index++;
    return obj->values[obj->index];
}

bool bSTIteratorHasNext(BSTIterator* obj) {
    return obj->index + 1 < obj->size;
}

char* solution(char** commands, int commandsSize, int** values, int valuesSize) {
    static char result[1000];
    strcpy(result, "[null");
    
    // Simplified example
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 7;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 3;
    root->left->left = root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 15;
    root->right->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->left->val = 9;
    root->right->left->left = root->right->left->right = NULL;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 20;
    root->right->right->left = root->right->right->right = NULL;
    
    BSTIterator* iterator = bSTIteratorCreate(root);
    
    for (int i = 1; i < commandsSize; i++) {
        if (strcmp(commands[i], "next") == 0) {
            int val = bSTIteratorNext(iterator);
            char temp[20];
            sprintf(temp, ",%d", val);
            strcat(result, temp);
        } else if (strcmp(commands[i], "hasNext") == 0) {
            bool has = bSTIteratorHasNext(iterator);
            strcat(result, has ? ",true" : ",false");
        }
    }
    
    strcat(result, "]");
    return result;
}

int main() {
    printf("[null,3,7,true,9,true,15,true,20,false]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Initial traversal visits all n nodes once, then O(1) per operation

✓ Linear Growth

Space Complexity

O(n)

Array stores all n values from the tree

⚡ Linearithmic Space

157.6K Views

Medium-High Frequency

~25 min Avg. Time

3.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Pre-compute All Values — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler