the # of internal nodes

Question

THis Q is in data structures that is:

Write a recursive algorithm that will, given the root node of a tree, calculate the number of internal nodes of the tree?

the internal nodes is

                 root
                  /\
    internal nodes  internal nodes
         / \              / \ 
    leaf   leaf       leaf   internal nodes
                                 /
                               leaf

I know how to calculate all the tree's node... but this time I want the number of internal nodes.... I hope there is answer for that...

Answer 1

Number of nodes? You can simply calculate this. Root don't have any parents, you can find it easy iterating over your nodes list propably?

Answer 2

Based on your definition of internal node the answer must be:

Internal Nodes = TotalNodes - LeafNodes - 1

The minus 1 is because, by the definition the root-node is not internal.

So see if you can break it into two calculations, count all nodes, and count leaf nodes.

When you have done that, you can see if you can come up with a way that enables you to figure it out in one traversal.

Answer 3

It sounds like you already have a recursive algorithm for counting total nodes... Basically, you need to modify that recursive algorithm to leave out leaf nodes. In the recursion function you should be returning a value that indicates the number of nodes the subtree starting at the present node contains. When you reach the base case (ie a leaf node), simply don't add the node (ie return a 0, as the subtree starting at the leaf node has 0 elements).

Answer 4

Internal nodes are nodes with both a parent node and a child node. Iterate through your tree (starting at the root node) and whenever you come across a node with both a parent node and child node, count it. You'll end up not counting the root node and leaf nodes.