inorder iterator for binary tree - java

Question

Here is my Node class:

private class Node {
    private int key;         // the key field
    private Object data;     // the rest of the data item
    private Node left;       // reference to the left child/subtree
    private Node right;      // reference to the right child/subtree
    private Node parent;     // reference to the parent

.. and so on.

This is the inorder iterator with next() and hasNext() methods:

private class inorderIterator implements LinkedTreeIterator {

    private Node nextNode;

    private inorderIterator() {
        // The traversal starts with the root node.
        nextNode = root;
        if(nextNode == null)
           return;
        while (nextNode.left != null)
           nextNode = nextNode.left;
    }

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

    public int next() {
        if(!hasNext()) 
            throw new NoSuchElementException();             

        Node r = nextNode;

        if (nextNode.right != null) {
            nextNode = nextNode.right;

            while (nextNode.left != null) {
                nextNode = nextNode.left;
            }

            return r.key;
        } else while (true) {
            if (nextNode.parent == null) {
                nextNode = null;
                return r.key;
            }

            if (nextNode.parent.left == nextNode) {          
                nextNode = nextNode.parent;
                return r.key;    
            }

            nextNode = nextNode.parent;                   
        }            
        return r.key; 
    }
}

The problem is, it only ever prints the left nodes on the left sub-tree. For example, for a tree with root node 17, left node 15 and right node 19, it only prints 15.
So it never enters a right subtree.

I'm guessing the problem is with the else while (true) portion, but I can't figure out how to fix this.

Answer 1

You could try a recursive approach.

Something like:

public void printTreeInOrder(Node node){
   if(node.left != null){
      printTree(node.left);
   }
   System.out.println(node.key);
   if(node.right != null){
      printTree(node.right);
   } 
}

If you passed this method the root node it should print out the entire tree for you.

I hope this helps.

Best.

Answer 2

Turns out that the parent field of my nodes was not being updated properly. Once that was fixed, the iterator worked properly.

Answer 3

I would use a stack with this helper method:

Node advance_to_min(Node r)
  {
    while (r.left != null)
      {
        s.push(r);
        r = r.left;
      }
    return r;
  }

The first node inorder is given by the call to this method on the root. Something like:

curr = advance_to_min(curr);

And then I would implement next() thus:

void next()
  {
    curr = curr.right;
    if (curr != null)
      {
        curr = advance_to_min(curr);
        return;
      }

    if (s.is_empty())
      curr = null;
    else
      curr = s.pop();
  }

curr and the stack s would be iterator attributes. curr would point to the current node in the inorder sequence.

The cost O(lg n) at worst case for each next() call (if the tree tends to be balanced) and the approach does not require parent pointers; so, it would have the same space cost than using parent pointers but only in the worst case