• C

count internal nodes in a tree

write a program in 'C' language to count the number of internal nodes  of a tree.
jessu2607Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

 
sunnycoderCommented:
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
0
 
skypalaeCommented:
Is it binary tree? If yes, then number of internal nodes is allways one less then number of leaves.

Cheers! S.
0
 
ankuratvbCommented:
The simplest solution would be a recursive function.
jessu2607,all this requires is one recursive fn. to be written.

Try it urself.As sunny said,if you are stuck,we'll be glad to help.
0

Experts Exchange Solution brought to you by ConnectWise

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

 
twobitadderCommented:
>>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.
0
 
skypalaeCommented:
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.
0
 
twobitadderCommented:
>/\
> /\
>  /\
>   /\
>    /\
>
>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
0
 
skypalaeCommented:
>     /\
>   /\ /\
> /

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.
0
 
ankuratvbCommented:
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.
0
 
Fippy_DarkpawCommented:
Here's an easy (not necessarily optimal) way:

- search every node in the tree
- if it has children then InternalNodeCount++
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.