A question on getting number of nodes in a Binary Tree

Question

Dear all,

I have written up two functions (pseudo code) for calculation the number of nodes and the tree height of a Binary Tree,given the root of the tree. Most importantly,the Binary Tree is represented as the First chiled/next sibling format.

so

struct TreeNode
{
  Object element;
  TreeNode *firstChild;
  TreeNode *nextSibling;
}

Calculate the # of nodes:

public int countNode(TreeNode root)
{
     int count=0;
     while(root!=null)
     {
        root= root.firstChild;
        count++;
     }

      return count;
}

public int countHeight(TreeNode root)
{
     int height=0;
     while(root!=null)
     {
        root= root.nextSibling;
        height++;
     }

  return height;

}

This is one of the problem I saw on an algorithm book,and my solution above seems to have some problems,also I didn't quite get the points of using this First Child/right sibling representation of Binary Tree,could you guys give me some idea and feedback,please? Cheers!

Answer 1

While literally correct, 'first child' and 'right sibling' can be a bit confusing. If you replace those with 'left child' and 'right child', I think you'll be able to understand it a bit better.

Answer 2

The use of next sibling and first child can be probably visualized like this:

A1 -- A2 -- A3
|     |    
|     B1 -- B2 -- B3
|           |
D1 -- D2    C1

The horizontal lines in the diagram represent nextSibling and the vertical lines correspond to firstChild link. For some problems, this may be natural visualization (but for some other problems, you may prefer usual tree with two sub-nodes - they are equivalent).

Your pseudo-code seems to be missing something, as you aren't really counting anything. I suppose you wanted to have count++, respectively height++ in the while loop.

Anyway, to count the number of nodes, you need to add the number of nodes of the child as well as the number of nodes on the same level (siblings). For reasonably small trees, this can be done recursively:

public int countNode(TreeNode root) { 
  if (root == null) return 0;
  return 1 + countNodes(root.firstChild) 
           + countNodes(root.nextSibling);
}

For larger data structures, you'll need to store the nodes "to be processed" in an in-memory stack to avoid stack overflow (sic!)

To count the height, you first need to decide how is the height defined. Is it the path when you follow firstChild links (that is A1 -> D1) or do you want the longest path in the tree (anywhere) (which would be A1 -> A2 -> B1 -> B2 -> C1). In the first case, your implementation would be correct. In the second case, you'd need a recursive function similar to the one for counting nodes (instead of adding, you'd pick the larger sub-tree).

Answer 3

To understand recurson, one must first understand recursion.

public int countNode(TreeNode root) 
{ 
     if (root==null) { 
        return 0;
     } else {
        return countNode(root.firstChild) + countNode(root.nextSibling) + 1;
     }
}

public int countHeight(TreeNode root) 
{ 
     if (root==null) { 
        return 0;
     } else {
        return max(countHeight(root.firstChild),
                   countHeight(root.nextSibling)) + 1;
     }
}

If the tree is null, it contains no nodes and has no height.

If the tree is not null, then it is one node taller than its taller subtree, and it contains all of the nodes of both subtrees, plus the node that contains the two subtrees.

Read Dave Touretzky's book on LISP. Dave teaches recursion using dragon stories, and the dragon is actually quite a good teacher.