recursion - Counting nodes in a tree in Java

Question

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

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;
}