LeetCode – Binary Search Tree Iterator (Java)

Tags: , , , ,

Binary Search Tree Iterator

  • Difficulty: Medium

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Source: https://leetcode.com/problems/binary-search-tree-iterator/

In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree. 

Analyis

Since “Calling next() will return the next smallest number in the BST”, it is actually an in order traverse of the binary search tree.  It is easy to implement the in order binary search tree traversal algorithm using a stack. However, to build a iterator for a binary search tree, we need to figure out which part of the code should be put into the hasNext() method, and which part of the code should be put into the next() method. 

Since we start from the root of tree, we can first push all the left children of root to the stack, now we know the top of the stack is the minimum value of the tree.

The code is like this:

In the hasNext() method, we simply check whether the stack is empty. 

In the next() method, we first pop up the stack to get the node, which is the current smallest node. Then we need to check whether this node has right child. If it does have right child, we need to put its right child and the right child’s left branch to the stack. After this process, the top of the stack holds the next smallest node. 

Here is the full implementation of the Binary Search Tree Iterator in Java: