Binary Search Tree (BST) Iterator

BST Iterator - InterviewBit

Problem: Implement two methods on a BST:
1. next()- returns the next minimum value
2. hasNext() — returns whether next minimum exists

Time and Space constraints:
1. next() and hasNext() should run in average O(1) time
2. Use O(h) memory, where h is the height of the tree.

Before we start off with solving the problem, let me give you some introduction to the keywords mentioned in the problem.

Amortized Time Complexity:

Amortized time complexity is used when an algorithm has an expensive operation only once in a while.
Let T1, T2, …, Tk be the complexities of a sequence of operations on a data structure. The amortized complexity of a single operation in this sequence is defined as (T1 + T2 + …+ Tk)/ k.

Height of a BST:

The height of a binary tree is defined as the number of edges in a path from the root node to the farthest leaf node.

Solution Approach

First thing to notice here is, we can only use O(h) space, which means, at any point of time, we can store only one root-leaf path in the memory.

Second, more obvious line of thought would be identifying the pattern of nodes with the minimum value in BST. Let us break it down to three steps:

Step1: By the unique binary search property of BST, which states that : key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree, the minimum value node would be the left-most node of the BST. In the above example, the left most node is 1, which is in-turn the minimum value in the BST.

Step2: Now that we have found out the minimum value node in the BST, let us take it one step forward, by figuring out which is the next minimum value node. Consider removing node with value 1, in the above example. In that state, the left-most node and the minimum value node would be 3, which sounds sensible because the parent of a left child in the BST is greater than the node but less than all the nodes to its right.

Step3: Now we are left with a bit more complicated state. We have got past 3, we need to return the next minimum. The answer will be pretty straightforward if we try to solve for the minimum value node in 3’s right subtree, i.e., find out the left-most node in that subtree, which is 4.

So once we take the left-most node in a tree and its parent, then the next minimum would the left-most child of the parent’s right subtree and its a recursive process from there.

Now let us dive deeper into the solution approach:

Since we have the liberty to store O(h) nodes in memory, let us think of maintaining a list, say minList, which contains the path from root to the left-most node. So initially the list would contain 8, 3, 1.

But we need to return the minimum node with an amortized time complexity O(1). Which is the data structure which will help us return the last pushed item in O(1)?

The key is to use a Stack to store the path of nodes. So let us rename our minList to minStack to be more clear.

Once we return the minimum value, the next minimum would be the value of the parent node (if the right subtree is null) or the value of the left-most child in the right subtree (if right subtree exists). In the latter case, the node is not yet pushed to our minStack.

Let’s say, the node we just popped out is N. Now, the job left for us, is to add all the nodes (excluding N) in the path from N to the left-most node of N’s right subtree.

In the above example, 1’s right subtree is null, so the next time we call next(), 3 would be popped and returned. Then all nodes in 3’s right subtree would be added to the minStack. State of minStack would then be: 8, 6, 4

The process would follow the same pattern from there.

public int next() {
        TreeNode popNode = minList.pop();
        int popVal = popNode.val;
        TreeNode popNodeRight = popNode.right;
        while(popNodeRight != null){
            this.minList.push(popNodeRight);
            popNodeRight = popNodeRight.left;
        }
        return popVal;
    }

Inorder to implement the hasNext() method, we just need to check if minStack is empty.

public boolean hasNext() {
        return !minList.empty();
    }

Time complexity explanation: Every node in the tree gets added to the stack exactly once. If next is called n times, the average time complexity reduces to O(1).
Space complexity explanation: At any point of time, at most h nodes will be present in the minStack, as we are concentrating on one root to leaf path at a time.

Complete Solution: