Recursive algorithm for tree

Question

Possible Duplicate:
the # of internal nodes

I'm taking course that's Data Structure in CS. I've this question that asks for a recursive algorithm that determines the height of the tree by given the ROOT NODE of the tree. I'll explain what is tree and root node:

                                  root
                                   / \
                     internal node   internal node
                         / \                  \
             external node  internal node     external node
                                  /                 
                           external node

what I've done so far is :

• input: int r (r= the root node) T is tree
• output: int h (h= the hight of tree)

• hight(T,r):

• if r is a root node of T then

• return 1
• else
• h<---1
• for each child w of r in T do
• h<---max(h, hight(T,w))

• return 1+h

that what I get so far....

Answer 1

Since this is homework, I don't want to give away the solution, but here's a hopefully helpful hint.

Focus on just the very top of the tree, with your root node and the children right below it. If you know the heights of the subtrees, how does that help you compute the height of the parent tree?

In the example you gave, imagine that you knew the heights (marked with [square brackets]) of the subtrees and wanted to find the height of the root tree:

                              root[?]
                               / \
               internal node[3] internal node[2]
                     / \                  \
         external node  internal node     external node
                              /                 
                       external node

Another hint is that your code will have the following structure, which is common to recursive programs. You will have a base case and then an inductive step in which you represent your problem in terms of smaller sub-problems.

int height(Node root) {
  // The base case is that the node has no children, so it is a tree of height 1.
  if (root has no children) return 1;

  // Otherwise, apply the hint from above. Remember, you can call this height()
  // function on the children of the root!
}