Counting nodes in a tree in Java

Question

Hi,

First of all, I swear this is not homework, it's a question I was asked in an interview. I think I made a mess of it (though I did realise the solution requires recursion). Here is the question:

Implement the count() method which returns the number of nodes in a tree. If a node doesn't have either a left or right child, the relevant getXXChild() method will return null

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
    // Implement me
  }
}

My reason for asking the question is simply curious to see the correct solution, and thereby measure how bad mine was.

Cheers, Tony

Answer 1

A trivial recursive solution:

int count() {
   Tree l = getLeftTree();
   Tree r = getRightTree();
   return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0);
}

A less trivial non-recursive one:

int count() {
    Stack<Tree> s = new Stack<Tree>();
    s.push(this);
    int cnt = 0;
    while (!s.empty()) {
        Tree t = s.pop();
        cnt++;
        Tree ch = getLeftTree();
        if (ch != null) s.push(ch); 
        ch = getRightTree();
        if (ch != null) s.push(ch); 
    }
    return cnt;
}

The latter is probably slightly more memory-efficient, because it replaces recursion with a stack and an iteration. It's also probably faster, but its hard to tell without measurements. A key difference is that the recursive solution uses the stack, while the non-recursive solution uses the heap to store the nodes.

Edit: Here's a variant of the iterative solution, which uses the stack less heavily:

int count() {
    Tree t = this;
    Stack<Tree> s = new Stack<Tree>();
    int cnt = 0;
    do {
        cnt++;
        Tree l = t.getLeftTree();
        Tree r = t.getRightTree();
        if (l != null) {
            t = l;
            if (r != null) s.push(r);
        } else if (r != null) {
            t = r;
        } else {
            t = s.empty() ? null : s.pop();
        }
    } while (t != null);
    return cnt;
}

Whether you need a more efficient or a more elegant solution naturally depends on the size of your trees and on how often you intend to use this routine. Rembemer what Hoare said: "premature optimization is the root of all evil."

Answer 2

Something like this should work:

int count()
{
    int left = getLeftChild() == null ? 0 : getLeftChild().count();
    int right = getRightChild() == null ? 0 : getRightCHild().count();

    return left + right + 1;
}

Answer 3

This is a standard recursion problem:

count():
    cnt = 1 // this node
    if (haveRight) cnt += right.count
    if (haveLeft)  cnt += left.count
return cnt;

Very inefficient, and a killer if the tree is very deep, but that's recursion for ya...

Answer 4

int count() {
  Tree right = getRightChild();
  Tree left = getLeftChild();
  int c = 1;                                      // count yourself!
  if ( right != null ) c += right.count();        // count sub trees
  if ( left != null ) c += left.count();          // ..
  return c;
}

Answer 5

return (getRightChild() == null ? 0 : getRightChild.count()) + (getLeftChild() == null ? 0 : getLeftChild.count()) + 1;

Or something like that.

Answer 6

You can count the tree by traversing it many ways. Simply preorder traversal, the code would be (based on the functions you defined):

int count() {
    count = 1;
    if (this.getLeftChild() != null)
        count += this.getLeftChild().count();
    if (this.getRightChild() != null)
        count += this.getRightChild().count();
    return count;
}

Answer 7

int count()

{
   int retval = 1;
    if(null != getRightChild()) retval+=getRightChild().count();
    if(null != getLeftChild()) retval+=getLeftChild().count();
    return retval;

}

God I hope I didn't make a mistake.

EDIT: I did actually.

Answer 8

I like this better because it reads:

return count for left + count for rigth + 1

  int count() {
      return  countFor( getLeftChild() ) + countFor( getRightChild() ) + 1;
  }
  private int countFor( Tree tree )  { 
       return tree == null ? 0 : tree.count();
  }

A little more towards literate programming.

BTW, I don't like the getter/setter convention that is so commonly used on Java, I think a using leftChild() instead would be better:

  return countFor( leftChild() ) + countFor( rightChild() ) + 1;

Just like Hoshua Bloch explains here http://www.youtube.com/watch?v=aAb7hSCtvGw at min. 32:03

If you get it rigth your code reads...

BUT, I have to admit the get/set convention is now almost part of the language. :)

For many other parts, following this strategy creates self documenting code, which is something good.

Tony: I wonder, what was your answer in the interview.

Answer 9

Of course, if you want to avoid visiting every node in your tree when you count, and processing time is worth more to you than memory, you can cheat by creating your counts as you build your tree.

1. Have an int count in each node, initialized to one, which respresents the number of nodes in the subtree rooted in that node.

2. When you insert a node, before returning from your recursive insert routine, increment the count at the current node.

i.e.

public void insert(Node root, Node newNode) {
  if (newNode.compareTo(root) > 1) {
    if (root.right != null) 
      insert(root.right, newNode);
    else
      root.right = newNode;
  } else {
    if (root.left != null)
      insert(root.left, newNode);
    else
      root.left = newNode;
  }
  root.count++;
}

Then getting the count from any point just involves a lookup of node.count

Answer 10

class Tree {

  Tree getRightChild() {
    // Assume this is already implemented
  }

  Tree getLeftChild() {
    // Assume this is already implemented
  }

  int count() {
   return 1 
      + getRightChild() == null? 0 : getRightChild().count()
      + getLeftChild() == null? 0 : getLeftChild().count();
  }
}

Answer 11

My first attempt didn't have anything new to add, but then I started to wonder about recursion depth and whether it would be possible to rearrange the code to take advantage of the tail call optimization feature of the latest Java compiler. The main problem was the null test - which can be solved using a NullObject. I'm not sure if TCO can deal with both recursive calls, but it should at least optimize the last one.

static class NullNode extends Tree {

    private static final Tree s_instance = new NullNode();

    static Tree instance() {
        return s_instance;
    }

    @Override
    Tree getRightChild() {  
        return null;
    }  

    @Override
    Tree getLeftChild() {  
        return null;
    }  

    int count() {  
        return 0;
    }
}

int count() {      
    Tree right = getRightChild();      
    Tree left  = getLeftChild();      

    if ( right == null ) { right = NullNode.instance(); }
    if ( left  == null ) { left  = NullNode.instance(); }

    return 1 + right.count() + left.count();
}   

The precise implementation of NullNode depends on the implementations used in Tree - if Tree uses NullNode instead of null, then perhaps the child access methods should throw NullPointerException instead of returning null. Anyway, the main idea is to use a NullObject in order to try to benifit from TCO.