Given the root of a Binary Search Tree, implement an Inorder Iterator with methods hasNext() and next().

1. Introduction

In this article, I will discuss how to create a Binary Search Tree iterator. We can also use this iterator for Binary Tree Iterator or Inorder iterator.

This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.

2. Content

Below is an example of the Binary Search Tree and its Inorder Traversal.

Example 1: Complete Binary Search Tree

Inorder Traversal = [2,5,7,10,12,15,17]

Example 2: Skewed Binary Search Tree

Inorder traversal = [10,11,15,19,29]

3. Iterator for Binary Search Tree

1. We will name our class as a BSTIterator. The root node will be input to a parameterized constructor.

Class signature:

class BSTIterator {
    private TreeNode temp;

    public BSTIterator(TreeNode root) {
        temp = root;
    }
}

2. We will need an auxiliary data structure to store the elements that we will traverse in the tree. Let us use the ArrayDeque class.

class BSTIterator {
    private TreeNode temp;
    private final Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        temp = root;
    }
}

3. In Inorder traversal, we insert the node’s left subtree into the stack and then traverse its root and then its right subtree. If the right subtree’s left subtree exists, then we insert that into the stack and so on. So now we need a method that will insert the left subtree into the stack.

void pushLeftSubTree(TreeNode temp) {
   while (temp != null) {
       stack.push(temp);
       temp = temp.left;
   }
}

4. Implementing hasNext() method.

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

5. Implementing next() method. We need to pop() the node from the stack and return the value of that node. Before we return the value, we need to traverse the right subtree hence, we call method pushLeftSubTree() with the popped value’s right subtree.

public int next() {
    temp = q.pop();
    pushLeftSubTree(temp.right);
    return temp.val;
}

Entire implementation:

class BSTIterator {
    
    private final Deque<TreeNode> stack;
    private TreeNode temp;
    
    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        temp = root;
        pushLeftSubTree(temp);
    }
    
    void pushLeftSubTree(TreeNode temp) {
        while(temp != null) {
            stack.push(temp);
            temp = temp.left;
        }
    }
    
    public int next() {
        temp = stack.pop();
        pushLeftSubTree(temp.right);
        return temp.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

Time Complexity:

1. hasNext() method: O(1) as we are just checking if the stack is empty or not.
2. next() method: This is tricky. In the next() method, we pop an element and return it. This takes O(1) time. But the pushLeftSubTree(node.right) can take a longer time. If the tree is skewed from this node, then it will take linear time, i.e. O(n) where n is the total number of nodes in the Binary Search Tree. As each node gets pushed and popped exactly once while iterating n nodes that is 2n * O(1) so on average O(1) for operation on the next() method.

Space Complexity:

1. O(n) where n is the total number of nodes in the Binary Search Tree.

4. Conclusion

In this article, we saw Inorder Traversal of the Binary Tree using Recursion and Iteration.

Github Link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/BSTIterator.java