Finding the levels of a Binary tree

[JC]

Hello,

Does anyone know how to get the level(s) in a binary tree.

For example:

(60) Level 0
/ \
(50) (65) Level 1
/ \ \
(49) (55) (68) Level 2
\
(71) Level 3

I tried counting all the "left" or "right" leaves but that doesn't work.
because of children.

Any help would be greatly appreciated.
JC

 

[White Wolf]

Hello,

Does anyone know how to get the level(s) in a binary tree.

For example:

(60) Level 0
/ \
(50) (65) Level 1
/ \ \
(49) (55) (68) Level 2
\
(71) Level 3

I tried counting all the "left" or "right" leaves but that doesn't work.
because of children.

How about walking the whole tree and after every step down-tree storing away
the depth if it is bigger than the old max. Seems like a simple maximum
value search - with tree walking added.

 

[Victor Bazarov]

Does anyone know how to get the level(s) in a binary tree.

For example:

(60) Level 0
/ \
(50) (65) Level 1
/ \ \
(49) (55) (68) Level 2
\
(71) Level 3

I tried counting all the "left" or "right" leaves but that doesn't work.
because of children.

Counting leaves and counting levels is not the same thing.

Any help would be greatly appreciated.

You probably need recursive traversing of the tree with keeping
the maximum depth in a variable. Every time you reach a leaf,
compare the maximum depth with its depth. Adjust the maximum
depth if needed. BTW, what's your C++ _language_ question?

Victor

 

[Gianni Mariani]

Hello,

Does anyone know how to get the level(s) in a binary tree.

For example:

(60) Level 0
/ \
(50) (65) Level 1
/ \ \
(49) (55) (68) Level 2
\
(71) Level 3

I tried counting all the "left" or "right" leaves but that doesn't work.
because of children.

Any help would be greatly appreciated.

struct node
{
node * branches[ 2 ];

int depth()
{
int thisdepth = 1;

if ( branches[ 0 ] )
{
thisdepth = max( thisdepth, 1 + max( branches[0].depth() );
}

if ( branches[ 1 ] )
{
thisdepth = max( thisdepth, 1 + max( branches[1].depth() );
}

return thisdepth;
}
};