You need to implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST). The iterator provides two main functions. The next() function must return the next smallest number in the BST. The hasNext() function must return true if there are still unexplored numbers remaining in the tree, and false otherwise. The iterator is initialized with the root of the tree, and the pointer conceptually starts right before the smallest element.
Example 1
Input: Tree: root = [7, 3, 15, null, null, 9, 20]
Calls: BSTIterator, next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()
Output: [null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation: explanation in order of each call :
The in-order traversal of this tree produces the sorted sequence: 3, 7, 9, 15, 20.
The first
next()call returns the smallest element, 3.The second
next()returns 7.hasNext()returns true because 9, 15, and 20 are still pending.We continue calling
next()until we retrieve 20.The final
hasNext()returns false because all elements have been exhausted.
Brute Force Approach
The simplest way to supply items in a specific order is to pre-calculate the entire order upfront. Think about preparing for a presentation. Instead of fetching data from the internet live while you are speaking, you download all the slides beforehand and put them in a strict sequence. During the presentation, you simply click "next" to show the next slide. We can do the exact same thing by performing a complete in-order traversal of the tree immediately upon initialization, storing all the values in a standard array list.
Algorithm
Create a dynamic array (or list) inside the class to hold the tree values.
Maintain an integer
indexvariable starting at 0 to track our current position in the list.In the constructor, write a standard recursive in-order traversal function that visits every node and pushes its value into the array.
For the
next()function, simply return the value located at the currentindexinside the array, and then increment theindexby 1.For the
hasNext()function, check if theindexis strictly less than the total length of the array. If it is, there are more elements left.
Dry Run
BST Iterator Brute Dry Run
Solution
// C++ program to implement Binary Search Tree Iterator#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class BSTIterator {private: // Array to store the flattened tree values vector<int> nodesSorted; // Pointer to track the current sequence position int index; // Standard recursive in-order traversal to populate the array void inorder(TreeNode* root) { if (root == nullptr) { return; } inorder(root->left); nodesSorted.push_back(root->val); inorder(root->right); }public: // Constructor initializes the array and fills it completely BSTIterator(TreeNode* root) { index = 0; inorder(root); } // Retrieves the current element and advances the internal pointer int next() { int val = nodesSorted[index]; index++; return val; } // Checks if the internal pointer has reached the end of the array bool hasNext() { return index < nodesSorted.size(); }};// Driver code starts hereint main() { // Construct the sample tree TreeNode* root = new TreeNode(7); root->left = new TreeNode(3); root->right = new TreeNode(15); root->right->left = new TreeNode(9); root->right->right = new TreeNode(20); // Instantiate the iterator object BSTIterator* obj = new BSTIterator(root); // Simulate iterator calls cout << obj->next() << endl; // 3 cout << obj->next() << endl; // 7 cout << (obj->hasNext() ? "true" : "false") << endl; // true cout << obj->next() << endl; // 9 return 0;}Complexity Analysis
Time Complexity: O(N) for initialization, because traversing the entire tree to fill the array takes linear time. next() and hasNext() strictly take O(1) time.
Space Complexity: O(N), because we duplicate the entire tree's values inside a separate dynamic array, scaling directly with the total number of nodes.
Optimal Approach
The brute force approach works, but requires massive memory allocation. If a tree has ten million nodes, flattening it immediately creates an array of ten million items, consuming huge amounts of RAM right from the start. We can heavily optimize our memory by pausing the traversal. By manually controlling an explicit stack, we only ever store the nodes along the specific branch we are currently exploring, limiting our memory to the strict height of the tree. If you want to understand this in detail, check our guide on Inorder Traversal using Stacks.
Think about navigating a maze by always hugging the left wall. You walk down a long hallway, marking the intersections you pass, until you hit a dead end on the far left. That dead end is your first stop. When you are asked for the next stop, you trace your steps backward to the last intersection you marked. If a right-side hallway exists there, you step into it, and then instantly start hugging the left wall again to find the next absolute minimum spot. We use a stack to act as our physical memory of the intersections we passed.
Algorithm
Initialize an empty stack structure to hold tree nodes.
Create a helper function called
pushAllLeftthat takes a node, repeatedly pushes it onto the stack, and moves to its left child until it hits a null dead end.In the constructor, call
pushAllLeftand pass the root node to load the initial far-left path.For the
hasNext()function, simply check if the stack is completely empty. If it holds nodes, there are items left to process.For the
next()function, pop the top node from the stack. This node is our current smallest value to return.Before returning the value, check if this popped node has a right child. If it does, call
pushAllLefton that right child to load its entire far-left path into the stack for future calls.Return the value of the popped node.
Dry Run
BST Iterator Optimal Dry Run
Solution
// C++ program to implement Binary Search Tree Iterator#include <bits/stdc++.h>using namespace std;// Definition for a binary tree nodestruct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};class BSTIterator {private: // Explicit stack to simulate and pause the recursion stack<TreeNode*> st; // Helper function to push the current node and all its left children void pushAllLeft(TreeNode* node) { while (node != nullptr) { st.push(node); node = node->left; } }public: // Constructor initializes the state by loading the leftmost path BSTIterator(TreeNode* root) { pushAllLeft(root); } // Retrieves the next smallest element and updates the stack state int next() { // The top of the stack is always the next smallest value TreeNode* topNode = st.top(); st.pop(); // If the processed node has a right branch, load its leftmost path if (topNode->right != nullptr) { pushAllLeft(topNode->right); } return topNode->val; } // Returns true as long as there are pending nodes in the stack bool hasNext() { return !st.empty(); }};// Driver code starts hereint main() { // Construct the sample tree TreeNode* root = new TreeNode(7); root->left = new TreeNode(3); root->right = new TreeNode(15); root->right->left = new TreeNode(9); root->right->right = new TreeNode(20); // Instantiate the iterator object BSTIterator* obj = new BSTIterator(root); // Simulate iterator calls cout << obj->next() << endl; // 3 cout << obj->next() << endl; // 7 cout << (obj->hasNext() ? "true" : "false") << endl; // true cout << obj->next() << endl; // 9 return 0;}Complexity Analysis
Time Complexity: Average O(1) for both next() and hasNext(). Although traversing down the left branch contains a while loop, each node in the tree is pushed and popped exactly once across the entire lifecycle of the iterator. Distributing this total cost over all N elements results in an amortized O(1) time per operation.
Space Complexity: O(h), where h is the height of the tree. At any given moment, the stack only holds the nodes along a single path from the root down to a leaf, which drastically minimizes RAM usage compared to flattening the whole tree.
Interview follow-up Questions
The core rule of an in-order traversal is "Left, Root, Right". The absolute smallest value in a BST is guaranteed to be at the extreme bottom left. By pushing all left children onto the stack right away, we guarantee that the element sitting at the top of the stack is the immediate next smallest element ready to be processed.
Be the first to add a comment.