In-order iterator for binary tree [closed]

Question

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?

Answer 1

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 

• The first element is "fully left from the root"
• 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 subtree
• c 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.