Last updated on February 2nd, 2025 at 05:55 am

Here, we see a Binary Search Tree Iterator LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Design, Stack, Tree

Companies

Facebook, Google, LinkedIn, Microsoft

Level of Question

Medium

Binary Search Tree Iterator LeetCode Solution

1. Problem Statement

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.

Example 1:

Input [“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output [null, 3, 7, true, 9, true, 15, true, 20, false]
Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // return 3
bSTIterator.next(); // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next(); // return 20
bSTIterator.hasNext(); // return False

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Tree Depth First Search (DFS) with Stack”. This pattern is used to traverse a binary search tree (BST) in an iterative manner using a stack to simulate the recursive DFS traversal. The code leverages the properties of a BST (left subtree contains smaller values, right subtree contains larger values) to implement an in-order traversal.

3. Code Implementation in Different Languages

3.1 Binary Search Tree Iterator C++

class BSTIterator {
    stack<TreeNode *> myStack;
public:
    BSTIterator(TreeNode *root) {
        pushAll(root);
    }

    bool hasNext() {
        return !myStack.empty();
    }
    
    int next() {
        TreeNode *tmpNode = myStack.top();
        myStack.pop();
        pushAll(tmpNode->right);
        return tmpNode->val;
    }

private:
    void pushAll(TreeNode *node) {
        for (; node != NULL; myStack.push(node), node = node->left);
    }
};

3.2 Binary Search Tree Iterator Java

class BSTIterator {
    private Stack<TreeNode> stack = new Stack<TreeNode>();
    public BSTIterator(TreeNode root) {
        pushAll(root);
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    public int next() {
        TreeNode tmpNode = stack.pop();
        pushAll(tmpNode.right);
        return tmpNode.val;
    }
    
    private void pushAll(TreeNode node) {
        for (; node != null; stack.push(node), node = node.left);
    }
}

3.3 Binary Search Tree Iterator JavaScript

var BSTIterator = function(root) {
    if(!root){
        this.data = [];
        return;
    }
    let visited = [];
    function traverse(node){
        if(node.left) traverse(node.left);
        visited.push(node.val);
        if(node.right) traverse(node.right);
    }
    traverse(root);
    this.data = visited.reverse();
};

BSTIterator.prototype.next = function() {
    return this.data.pop();
};

BSTIterator.prototype.hasNext = function() {
    return this.data.length > 0 ;
};

3.4 Binary Search Tree Iterator Python

class BSTIterator(object):
    def __init__(self, root):
        self.stack = list()
        self.pushAll(root)

    def hasNext(self):
        return self.stack

    def next(self):
        tmpNode = self.stack.pop()
        self.pushAll(tmpNode.right)
        return tmpNode.val
        
    def pushAll(self, node):
        while node is not None:
            self.stack.append(node)
            node = node.left