BST iterator

Intuition

When performing an inorder traversal on a Binary Search Tree (BST), the result is a sorted list of node values. By storing these values in an array, it's possible to easily access them in ascending order. The BSTIterator class leverages this idea by maintaining an index to track the current position within the array. This index is initialized to -1, and with each call to next(), the index is incremented to provide the next element in the sorted sequence.

Approach

Execute an inorder traversal of the BST and store the node values in an array. This involves recursively visiting the left subtree, the current node, and then the right subtree.
In the BSTIterator() constructor, initialize an index variable to -1. This variable will keep track of the current position within the array.
Implement the next() function to increment the index by 1 and return the value at the updated index from the inorder traversal array.
Implement the hasNext() function to return true if index + 1 is less than the length of the inorder traversal array; otherwise, return false.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

//Definition for a binary tree node.
 struct TreeNode {
     int data;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};


// Class for BST Iterator
class BSTIterator {
public:
    // Constructor to initialize the iterator
    BSTIterator(TreeNode* root) {
        // Perform inorder traversal and store values
        inorderTraversal(root);
        // Initialize index to -1 (before first element)
        index = -1;
    }
    
    // Check if there are more elements in the BST
    bool hasNext() {
        // True if there are more elements
        return index + 1 < values.size();
    }
    
    // Return the next element in the BST
    int next() {
        // Increment index and return the next value
        return values[++index];
    }

private:
    // Vector to store inorder traversal values
    vector<int> values;
    // Index to track the current position
    int index;

    // Helper function to perform inorder traversal
    void inorderTraversal(TreeNode* node) {
        // Base case: if node is null, return
        if (node == nullptr) return;
        // Recur on the left subtree
        inorderTraversal(node->left);
        // Add the current node's value to the vector
        values.push_back(node->data);
        // Recur on the right subtree
        inorderTraversal(node->right);
    }
};

// Main method to demonstrate the usage of BSTIterator
int main() {
    // Create a sample binary search 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 BSTIterator with the root of the tree
    BSTIterator* iterator = new BSTIterator(root);

    // Use the iterator to get the elements in sorted order
    while (iterator->hasNext()) {
        cout << iterator->next() << " ";
    }

    // Output: 3 7 9 15 20

    return 0;
}
import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
public class TreeNode {
     int data;
     TreeNode left;
     TreeNode right;
     TreeNode(int val) { data = val; left = null; right = null; }
}


// Class for BST Iterator
class BSTIterator {
    // List to store inorder traversal values
    private List<Integer> values; 
    // Index to track the current position
    private int index;            

    // Constructor to initialize the iterator
    public BSTIterator(TreeNode root) {
        // Initialize the list
        values = new ArrayList<>(); 
        // Perform inorder traversal and store values
        inorderTraversal(root);     
        // Initialize index to -1 (before first element)
        index = -1;                 
    }

    // Check if there are more elements in the BST
    public boolean hasNext() {
        // True if there are more elements
        return index + 1 < values.size();
    }

    // Return the next element in the BST
    public int next() {
        // Increment index and return the next value
        return values.get(++index);
    }

    // Helper function to perform inorder traversal
    private void inorderTraversal(TreeNode node) {
        // Base case: if node is null, return
        if (node == null) return;
        // Recur on the left subtree
        inorderTraversal(node.left);
        // Add the current node's value to the list
        values.add(node.data);
        // Recur on the right subtree
        inorderTraversal(node.right);
    }
}


// Main method to demonstrate the usage of BSTIterator
public class Main {
    public static void main(String[] args) {
        // Create a sample binary search 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 BSTIterator with the root of the tree
        BSTIterator iterator = new BSTIterator(root);

        // Use the iterator to get the elements in sorted order
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }

        // Output: 3 7 9 15 20
    }
}

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.data = val
        self.left = left
        self.right = right

class BSTIterator:
    def __init__(self, root): 
        # Initialize the BSTIterator with the root of the BST.
        # List to store inorder traversal values
        self.values = []  
        # Index to track the current position
        self.index = -1  
        # Perform inorder traversal and store values
        self.inorderTraversal(root)  

    def hasNext(self):
        # Return True if there are more elements in the BST.
        return self.index + 1 < len(self.values)

    def next(self):
        # Return the next element in the BST.
        self.index += 1
        return self.values[self.index]

    def inorderTraversal(self, node):
        # Helper function to perform inorder traversal.
        if node is None:
            return
        self.inorderTraversal(node.left)
        self.values.append(node.data)
        self.inorderTraversal(node.right)

# Main method to demonstrate the usage of BSTIterator
if __name__ == "__main__":
    # Create a sample binary search tree
    root = TreeNode(7)
    root.left = TreeNode(3)
    root.right = TreeNode(15)
    root.right.left = TreeNode(9)
    root.right.right = TreeNode(20)

    # Instantiate the BSTIterator with the root of the tree
    iterator = BSTIterator(root)

    # Use the iterator to get the elements in sorted order
    while iterator.hasNext():
        print(iterator.next(), end=" ")

    # Output: 3 7 9 15 20
// Definition for a binary tree node.
class TreeNode {
    constructor(val = 0, left = null, right = null){
        this.data = val;
        this.left = left;
        this.right = right;
    }
}

class BSTIterator {
    constructor(root) {
        // Array to store inorder traversal values
        this.values = []; 
        // Index to track the current position
        this.index = -1;  
        // Perform inorder traversal and store values
        this.inorderTraversal(root); 
    }

    hasNext() {
        // True if there are more elements
        return this.index + 1 < this.values.length;
    }

    next() {
        // Increment index and return the next value
        return this.values[++this.index];
    }

    inorderTraversal(node) {
        // Base case: if node is null, return
        if (node === null) return;
        // Recur on the left subtree
        this.inorderTraversal(node.left);
        // Add the current node's value to the array
        this.values.push(node.data);
        // Recur on the right subtree
        this.inorderTraversal(node.right);
    }
}

// Main method to demonstrate the usage of BSTIterator
function main() {
    // Create a sample binary search tree
    const 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 BSTIterator with the root of the tree
    const iterator = new BSTIterator(root);

    // Use the iterator to get the elements in sorted order
    while (iterator.hasNext()) {
        console.log(iterator.next()); // Output: 3 7 9 15 20
    }
}

// Run the main method
main();

Complexity Analysis

Time Complexity O(N) where n is the number of nodes in the tree for inorder traversal and constant time O(1) for hasNext and next.

SpaceComplexity O(N) due to the storage of values from the inorder traversal in an array

Intuition

While a previous approach used O(N) space complexity, it can be optimized to O(H) space complexity, where H is the height of the tree, by utilizing the properties of a Binary Search Tree (BST). This method creates an iterator that uses a stack to manage the traversal, resulting in efficient O(1) time complexity for the next() and hasNext() operations. By initially traversing to the leftmost node and maintaining a stack of nodes, the BST can be iterated over efficiently.

Approach

Constructor BSTIterator(TreeNode root):
- Use a stack (Last In First Out) within the constructor.
- Start from the root and traverse to the leftmost node, pushing each encountered node onto the stack.
next() function:
- Pop the top element from the stack.
- Move to the right subtree of the popped node and traverse down its left subtree, pushing encountered nodes onto the stack.
- Return the value of the popped node.
hasNext() function:
- Check if the stack is not empty.
- If the stack contains elements, return true, indicating there are more nodes to iterate over.
- If the stack is empty, return false, indicating there are no more nodes to iterate over.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(NULL), right(NULL) {}
};

class BSTIterator {
    stack<TreeNode*> myStack;

public:
    // Constructor initializes the iterator on the root of the BST
    BSTIterator(TreeNode* root) {
        pushAll(root);
    }
    
    // Returns true if there is a next element in the iterator
    bool hasNext() {
        return !myStack.empty();
    }
    
    // Returns the next smallest element in the BST
    int next() {
        TreeNode* temp = myStack.top();
        myStack.pop();
        pushAll(temp->right);
        return temp->data;
    }

private:
    // Helper function to push all the left nodes onto the stack
    void pushAll(TreeNode* node) {
        for (; node != NULL; myStack.push(node), node = node->left);
    }
};

// Main function to demonstrate the BSTIterator
int main() {
    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);

    BSTIterator* iterator = new BSTIterator(root);
    while (iterator->hasNext()) {
        cout << iterator->next() << " ";
    }

    // Clean up memory
    delete iterator;
    delete root->left;
    delete root->right->left;
    delete root->right->right;
    delete root->right;
    delete root;

    return 0;
}
// Definition for a binary tree node
class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { data = val; left = null; right = null; }
}

class BSTIterator {
    private Stack<TreeNode> stack = new Stack<>();
    
    // Constructor initializes the iterator on the root of the BST
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }

    // Returns true if there is a next element in the iterator
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    // Returns the next smallest element in the BST
    public int next() {
        TreeNode temp = stack.pop();
        pushAll(temp.right);
        return temp.data;
    }

    // Helper function to push all the left nodes onto the stack
    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    public static void main(String[] args) {
        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);

        BSTIterator iterator = new BSTIterator(root);
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}
# Definition for a binary tree node.
class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.data = val
         self.left = left
         self.right = right

class BSTIterator:

    def __init__(self, root):
        # Initialize the iterator on the root of the BST      
        self.stack = []
        self._pushAll(root)

    def hasNext(self):
        # Returns true if there is a next element in the iterator     
        return len(self.stack) > 0

    def next(self):
        # Returns the next smallest element in the BST
        temp = self.stack.pop()
        self._pushAll(temp.right)
        return temp.data

    def _pushAll(self, node):
        # Helper function to push all the left nodes onto the stack
        # type node: TreeNode
       
        while node is not None:
            self.stack.append(node)
            node = node.left

# Main method to demonstrate the BSTIterator
if __name__ == "__main__":
    root = TreeNode(7)
    root.left = TreeNode(3)
    root.right = TreeNode(15)
    root.right.left = TreeNode(9)
    root.right.right = TreeNode(20)

    iterator = BSTIterator(root)
    while iterator.hasNext():
        print(iterator.next(), end=" ")
// Definition for a binary tree node.
class TreeNode {
     constructor(val = 0, left = null, right = null) {
         this.data = val;
         this.left = left;
         this.right = right;
     }
 }

class BSTIterator {
    constructor(root) {
        this.stack = [];
        this._pushAll(root);
    }

    // Returns true if there is a next element in the iterator
    hasNext() {
        return this.stack.length > 0;
    }

    // Returns the next smallest element in the BST
    next() {
        let temp = this.stack.pop();
        this._pushAll(temp.right);
        return temp.data;
    }

    // Helper function to push all the left nodes onto the stack
    _pushAll(node) {
        while (node !== null) {
            this.stack.push(node);
            node = node.left;
        }
    }
}

// Main method to demonstrate the BSTIterator
const main = () => {
    let 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);

    let iterator = new BSTIterator(root);
    while (iterator.hasNext()) {
        console.log(iterator.next());
    }
}

main();

Complexity Analysis

Time Complexity O(1)as next() and hasNext() occur is constant time, the element pushed onto the stack during traversal to the leftmost node and during subsequent traversals will take O(H) time for each traversal.

Space Complexity : O(H), where H is the height of the tree. This is because, in the worst case, the stack can contain all the nodes from the root to the leftmost leaf node

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code