Binary Search Tree Iterator II - Practice Coding Problems

Binary Search Tree Iterator II - 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.

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

int prev() - Moves the pointer to the left, then returns the number at the pointer.

Notice: 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() and prev() calls will always be valid.

Input & Output

Example 1 — Basic Iterator Operations

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

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

💡 Note: Initialize iterator with BST [7,3,15,null,null,9,20]. In-order traversal: 3,7,9,15,20. Iterator starts before first element, so first next() returns 3, then 7, then 9, then 15.

Example 2 — Bidirectional Navigation

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

› Output: [null, 3, 7, true, 3, true, 7]

💡 Note: After next() twice (3,7), hasPrev() is true. prev() goes back to 3, then next() moves forward to 7 again.

Example 3 — Edge Case with Single Node

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

› Output: [null, true, 5, false, false]

💡 Note: Single node BST. hasNext() is true initially, next() returns 5. After consuming the only element, hasPrev() is false (started before first element) and hasNext() is false.

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, next, hasPrev, and prev

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary search tree with in-order: 3,7,9,15,20

Iterator State

Track current position and support next/prev operations

Navigation

Move forward and backward through sorted sequence

Key Takeaway

🎯 Key Insight: Use two stacks to efficiently track navigation paths in both directions

Asked in

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

The key insight is to use two stacks to efficiently track predecessors and successors for bidirectional navigation. The two-stack approach provides O(1) amortized time complexity while using only O(h) space where h is tree height. Time: O(1) amortized, Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Precompute All Values	O(n)	O(n)	Store entire in-order traversal in array, use index pointer
Two-Stack Approach	O(1)	O(h)	Use two stacks to track predecessors and successors efficiently

Precompute All Values — Algorithm Steps

Step 1: Traverse BST in-order and store all values in array
Step 2: Maintain current index pointer starting at -1
Step 3: Implement methods using simple array access and bounds checking

Visualization

Tap to expand

Step-by-Step Walkthrough

In-Order Traversal

Visit all nodes: left subtree, root, right subtree

Store in Array

Collect values: [3, 7, 9, 15, 20]

Navigate with Index

Use index pointer for bidirectional movement

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;
};

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

void inorder(struct TreeNode* node, struct BSTIterator* iter) {
    if (!node) return;
    inorder(node->left, iter);
    
    if (iter->size >= iter->capacity) {
        iter->capacity *= 2;
        iter->values = realloc(iter->values, iter->capacity * sizeof(int));
    }
    iter->values[iter->size++] = node->val;
    
    inorder(node->right, iter);
}

struct BSTIterator* createIterator(struct TreeNode* root) {
    struct BSTIterator* iter = malloc(sizeof(struct BSTIterator));
    iter->capacity = 100;
    iter->values = malloc(iter->capacity * sizeof(int));
    iter->size = 0;
    iter->index = -1;
    inorder(root, iter);
    return iter;
}

bool hasNext(struct BSTIterator* iter) {
    return iter->index + 1 < iter->size;
}

int next(struct BSTIterator* iter) {
    iter->index++;
    return iter->values[iter->index];
}

bool hasPrev(struct BSTIterator* iter) {
    return iter->index > 0;
}

int prev(struct BSTIterator* iter) {
    iter->index--;
    return iter->values[iter->index];
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Initial in-order traversal visits all n nodes once

✓ Linear Growth

Space Complexity

O(n)

Array stores all n node values

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

890 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

Precompute All Values — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler