How can I write a Java iterator (i.e. needs the next
and hasNext
methods) that takes the root of a binary tree and iterates through the nodes of the binary tree in in-order fashion?
The first element of a subtree is always the leftmost one. The next element after an element is the first element of its right subtree. If the element does not have a right child, the next element is the element's first right ancestor. If the element has neither a right child nor a right ancestor, it is the rightmost element and it's last in iteration.
I hope my code is human readable and covers all cases.
public class TreeIterator {
private Node next;
public TreeIterator(Node root) {
next = root;
if(next == null)
return;
while (next.left != null)
next = next.left;
}
public boolean hasNext(){
return next != null;
}
public Node next(){
if(!hasNext()) throw new NoSuchElementException();
Node r = next;
// If you can walk right, walk right, then fully left.
// otherwise, walk up until you come from left.
if(next.right != null) {
next = next.right;
while (next.left != null)
next = next.left;
return r;
}
while(true) {
if(next.parent == null) {
next = null;
return r;
}
if(next.parent.left == next) {
next = next.parent;
return r;
}
next = next.parent;
}
}
}
Consider the following tree:
d
/ \
b f
/ \ / \
a c e g
a
does not have a right child, so the next element is "up until you come from left"b
does have a right child, so iterate b
's right subtreec
does not have a right child. It's parent is b
, which has been traversed. The next parent is d
, which has not been traversed, so stop here.d
has a right subtree. Its leftmost element is e
.g
has no right subtree, so walk up. f
has been visited, since we've come from right. d
has been visited. d
has no parent, so we cannot move further up. We have come from the rightmost node and we're done iterating.