We help IT Professionals succeed at work.

Check out our new AWS podcast with Certified Expert, Phil Phillips! Listen to "How to Execute a Seamless AWS Migration" on EE or on your favorite podcast platform. Listen Now

x

count internal nodes in a tree

jessu2607
jessu2607 asked
on
Medium Priority
1,227 Views
Last Modified: 2008-03-10
write a program in 'C' language to count the number of internal nodes  of a tree.
Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2006

Commented:
sorry we cannot do your homework for you

make some efforts ... post your code and if you are stuck on something specific, we will help

Commented:
Is it binary tree? If yes, then number of internal nodes is allways one less then number of leaves.

Cheers! S.
Unlock this solution and get a sample of our free trial.
(No credit card required)
UNLOCK SOLUTION
>>Is it binary tree? If yes, then number of internal nodes is allways one less then number of leaves.

Only if it is a complete and balanced tree.

Commented:
twobitadder,

I don't get what you mean by complete, but definitely it doesn't need to be balanced tree

/\
 /\
  /\
   /\
    /\

is not balanced at all and it still has 5 internals and 6 leaves

and if complete means that there is not

/\
  \
  /\

that tree is (almost) for nothing and you can allways get complete by deleting the uncomplete internal

S.
>/\
> /\
>  /\
>   /\
>    /\
>
>is not balanced at all and it still has 5 internals and 6 leaves

    /\
  /\ /\
/

has 4 internals and 4 leaves

whilst
   /\
  /\/\
 /\
has 4 internals and 5 leaves

Commented:
>     /\
>   /\ /\
> /

is incomplete (as far as i understand your term 'completeness'). and it is balanced (since there are no 2 paths from root to leaf that would differ by 2). i still insist on that (complete) binary tree has allways one less internals than leaves. and on that incomplete trees are for nothing (but studying purposes).

S.
Full Binary Tree Theorem

Theorem:  The number of leaves in a non-empty full binary  tree is one more than the number of internal nodes.  

Full binary tree:  each node either is a leaf or is an internal node with exactly two non-empty children

For proof,see:http://www.cz3.nus.edu.sg/~chenk/cz2102/notes5_1.htm

BTW, a complete binary tree is:

Complete binary tree:  If the height of the tree is d, then all levels except possibly level d are completely full.  The bottom level has all nodes to the left side.
Here's an easy (not necessarily optimal) way:

- search every node in the tree
- if it has children then InternalNodeCount++
Unlock the solution to this question.
Thanks for using Experts Exchange.

Please provide your email to receive a sample view!

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.