Leetcode 173. Binary Search Tree Iterator

Problem Explanation

In this problem, we are required to implement an iterator for a Binary Search Tree (BST).

The iterator will be initialized with the root of the BST. We are required to implement two methods:

  • next(): this method should return the next smallest value in the BST.
  • hasNext(): this method should return a boolean indicating if a next smallest value exists in the BST.

Nodes' values in a BST are ordered from left to right in ascending order, so the smallest number will be the leftmost node and the most significant, rightmost. Our BST Iterator should follow this traversal order.

The problem also specifies that the next() and hasNext() operations need to provide average constant time complexity and use memory proportional to the height of the tree (O(h)), where 'h' is the height of the tree.

Approach

The solution for this problem will use the in-order traversal of the BST and store the values in an array (vals in our case). In-order traversal visits the nodes in the BST in a sorted order (ascending order). Thus we get a sorted sequence of node values when a BST is traversed in in-order.

The next() method will return the next smallest number by returning the current value in the array and incrementing the index. The hasNext() method, on the other, will check if we have a next smallest number by confirming if the index 'i' is less than the size of the array.

Example: Let's walk through an example. Suppose we have this BST:

1
2
3         8 
4       /   \
5      3     10
6     / \      \
7    1   6      14 
8       /  \    /
9      4    7  13

In inorder traversal we have: 1 3 4 6 7 8 10 13 14

Now assuming we have initialized the BSTIterator with the root of the above BST.

Calling next() for the first time would give 1, the second time 3, the third time 4, and so on. Assuming that next() has been called thrice, a call to hasNext() will be true since we still haven't traversed all nodes of the BST. If next() has been called nine times, hasNext() will return false because there no more nodes to be traversed.

Python Solution

1
2python
3class Solution:
4    
5    def __init__(self, root):
6        self.inorder = self.inorderTraversal(root)
7        self.index = -1
8    
9    def inorderTraversal(self, root):
10        if root is None:
11            return []
12        
13        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
14
15    def next(self):
16        self.index += 1
17        return self.inorder[self.index]
18    
19    def hasNext(self):
20        return self.index+1 < len(self.inorder)

Java Solution

1
2java
3public class BSTIterator {
4    private List<Integer> nums = new ArrayList<Integer>();
5    private Iterator<Integer> it;
6    
7    public BSTIterator(TreeNode root) {
8        inorder(root);
9        it = nums.iterator();
10    }
11    
12    private void inorder(TreeNode root) {
13        if(root == null)
14            return;
15            
16        inorder(root.left);
17        nums.add(root.val);
18        inorder(root.right);
19    }
20    
21    public int next() {
22        return it.next();
23    }
24    
25    public boolean hasNext() {
26        return it.hasNext();
27    }
28}

JavaScript Solution

1
2javascript
3class BSTIterator {
4    constructor(root) {
5        this.inorder = this.inorderTraversal(root);
6        this.index = -1;
7    };
8    
9    inorderTraversal(root) {
10        if (root === null) {
11            return [];
12        }
13        return this.inorderTraversal(root.left).concat([root.val], this.inorderTraversal(root.right));
14    };
15
16    next() {
17        this.index += 1;
18        return this.inorder[this.index];
19    };
20    
21    hasNext() {
22        return this.index+1 < this.inorder.length;
23    };
24};

In the above solution, we initialize the iterator with the root node of the tree and calculate an inorder traversal which gives us a sorted array of the node values. This array is stored in the inorder property of the iterator object.

The next method is implemented to return the next smallest number from the array using an incrementing index, while the hasNext method checks if the index is less than the length of the array, indicating there are still values left to return.

Python, Java, and JavaScript solutions all follow the same approach. They first traverse the tree using inorder traversal to get all values in ascending order and then use an index to check and get the next smaller value. In each solution, the time and space complexity are as required in the problem O(h), where h is the height of the tree. The time complexity is constant time for the 'next' and 'hasNext' operations as it just requires an array lookup or comparison. The space complexity is O(h) as we're storing all numbers in an array, where 'h' is the height of the tree.

All three solutions satisfy the problem's requirements and constraints and they work correctly and efficiently for a binary search tree (BST). Note that the presented solutions assume a valid BST where all the left nodes are smaller and all the right nodes are larger than the root node. It, however, will not cover any other scenarios where the tree is not balanced, the tree nodes have unusual or non-integer values, or the tree has cyclic dependencies where a tree node points back to an ancestor node in a cycle.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫