java – In-order iterator for binary tree

java – In-order iterator for binary tree

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 elements first right ancestor. If the element has neither a right child nor a right ancestor, it is the rightmost element and its 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 bs right subtree
  • c does not have a right child. Its 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 weve 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 were done iterating.

To get the next entry, nextEntry(), for the iterator, I looked at snippets from java.util.TreeMap pasted below. In plain English, Id say you make sure the root node is not null first else return null. If it is not, vist the right node if it is not null. Then visit the left (if not null) and visit that ones left repeatedly in a while loop until hitting null. If the originial right node is null then instead of all that, visit the parent node if that is not null. Now enter a while loop where you vist the parent until its either null or the node youre currently visiting has its right (child) node equal to your last position. Now return whatever entry youre sittng on. Failing all those options, return the (original) root node. HasNext() merely checks if this next entry you are returning is null or not.

public final boolean hasNext() {
     return next != null;
}

final TreeMap.Entry<K,V> nextEntry() {
    TreeMap.Entry<K,V> e = next;
    if (e == null || e.key == fenceKey)
        throw new NoSuchElementException();
    if (m.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

java – In-order iterator for binary tree

Its pretty straight forward, for in-order traversal you visit the left child if there is one, then the root node, then the right child:

visit_node(node)
   if node.left: visit_node(node.left)
   // visit the root node
   if node.right: visit_node(node.right)

Diagram:

     a 
   /           (in-order traversal would give bac)
  b     c

Leave a Reply

Your email address will not be published.