Counting nodes in a tree in Java

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

java recursion tree

Edit Report

1 Answer

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.

Have an int count in each node, initialized to one, which respresents the number of nodes in the subtree rooted in that node.
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

answered 2009-02-13T22:13:55.457

Counting nodes in a tree in Java

1 Answer

Your Answer