Problem:
Binary Search Tree Iterator
Write a binary search tree iterator that iterates from the smallest element to the biggest element.
For example:
Given bst:
5
/ \
2 8
/ \ / \
1 3 6 9
MyIterator it = new MyIterator(root);
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
should print 1 2 3 5 6 8 9
The next() and hasNext() should have the amortized (average) time complexity O(1) and uses O(H) memory, where H is the height of the tree.
Solution:
convert the BST into an ArrayList then return the ArrayList's iterator won't satisfy the time complexity. We need to iterate in place. Slightly modifying the solution for another problem: inorder traversal bst iteratively, will achieve the goal with amortized O(1) time complexity and O(H) space complexity.
class Solution {
public static void main(String...args) {
Node root = new Node(5, new Node(2, new Node(1, null, null), new Node(3, null, null)),
new Node(8, new Node(6, null, null), new Node(9, null, null)));
MyIterator it = new MyIterator(root);
while(it.hasNext()) {
System.out.print(it.next()+ " ");
}
}
private static class MyIterator implements Iterator<Integer> {
private Stack<Node> stack;
public MyIterator(Node root) {
this.stack = new Stack<>();
while(root != null) {
stack.push(root);
root = root.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Integer next() {
Node t = stack.pop();
Node result = t;
t = t.right;
while(t != null) {
stack.push(t);
t = t.left;
}
return result.value;
}
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
public static void main(String...args) {
Node root = new Node(5, new Node(2, new Node(1, null, null), new Node(3, null, null)),
new Node(8, new Node(6, null, null), new Node(9, null, null)));
MyIterator it = new MyIterator(root);
while(it.hasNext()) {
System.out.print(it.next()+ " ");
}
}
private static class MyIterator implements Iterator<Integer> {
private Stack<Node> stack;
public MyIterator(Node root) {
this.stack = new Stack<>();
while(root != null) {
stack.push(root);
root = root.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Integer next() {
Node t = stack.pop();
Node result = t;
t = t.right;
while(t != null) {
stack.push(t);
t = t.left;
}
return result.value;
}
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time complexity O(1), space complexity O(H).
