Solved

count internal nodes in a tree

Posted on 2004-04-07
11
671 Views
Last Modified: 2008-03-10
write a program in 'C' language to count the number of internal nodes  of a tree.
0
Comment
Question by:jessu2607
  • 3
  • 2
  • 2
  • +2
11 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10772791
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
 
LVL 4

Expert Comment

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

Cheers! S.
0
 
LVL 9

Accepted Solution

by:
ankuratvb earned 125 total points
ID: 10773207
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
 
LVL 5

Expert Comment

by:twobitadder
ID: 10779108
>>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
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
LVL 4

Expert Comment

by:skypalae
ID: 10781004
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
 
LVL 5

Expert Comment

by:twobitadder
ID: 10783089
>/\
> /\
>  /\
>   /\
>    /\
>
>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
 
LVL 4

Expert Comment

by:skypalae
ID: 10783185
>     /\
>   /\ /\
> /

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
 
LVL 9

Expert Comment

by:ankuratvb
ID: 10783255
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
 
LVL 4

Expert Comment

by:Fippy_Darkpaw
ID: 10801260
Here's an easy (not necessarily optimal) way:

- search every node in the tree
- if it has children then InternalNodeCount++
0

Featured Post

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Why does module make constant click noise ? 9 125
How to align numbers in C using the %d 2 89
Problem to scan all sheets 3 95
Arduino EDI - Programming language 3 80
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

895 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now