Binary Search Tree Iterator

LeetCode Q 173 - Binary Search Tree Iterator

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.

Example:
[7, 3, 15, #, #, 9, 20]

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // return 3
iterator.next(); // return 7
iterator.hasNext(); // return true
iterator.next(); // return 9
iterator.hasNext(); // return true
iterator.next(); // return 15
iterator.hasNext(); // return true
iterator.next(); // return 20
iterator.hasNext(); // return false].

Solution

Solution 1:

let Stack store the whole tree in initialization.

Code:

Stack<TreeNode> stack;

public BSTIterator(TreeNode root) {
	stack = new Stack<>();
	buildStack(root);
}

private void buildStack(TreeNode node) {
	if (node == null) return;
	
	buildStack(node.right);
	stack.push(node);
	buildStack(node.left);
}

/ ** @return the next smallest number * /
public int next() {
	if (stack.isEmpty()) return -1;
	
	return stack.pop().val;
}

/** @return whether we have a next smallest number * /
public boolean hasNext() {
	return !stack.isEmpty();
}

Solution 2:

1. use Stack to store the left nodes at first.
2. when poping a node, push its right nodes and right nodes’ branch into the stack.

Code:

Stack<TreeNode> stack;

public BSTIterator(TreeNode root) {

	stack = new Stack<>();
	while (root != null) {
		stack.push(root);
		root = root.left;
	}
	
}

/ ** @return the next smallest number * /
public int next() {
	
	if (!hasNext()) return -1;

	TreeNode curr = stack.pop();
	TreeNode right = curr.right;

	while (right != null) {
		stack.push(right);
		right = right.left;
	}

	return curr.val;
}

/** @return whether we have a next smallest number * /
public boolean hasNext() {
	return !stack.isEmpty();
}