Depth of Binary Tree

[RAKHE]

I have come accross with the code for finding Depth of tree, i am
not
getting this, please anyone throw a light on this ....

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg


please explain in code level rather than theoratical level.


int depth(treenode *p)
{
if(p==NULL)return(0);
if(p->left){h1=depth(p->left);}
if(p=>right){h2=depth(p->right);}
return(max(h1,h2)+1);


}

 

[Dr Malcolm McLean]

I have come accross with the code for finding Depth of tree,  i am
not
int depth(treenode *p)
{
   if(p==NULL)return(0);
   if(p->left){h1=depth(p->left);}
   if(p=>right){h2=depth(p->right);}
   return(max(h1,h2)+1);

There's nothing much wrong with this.
h1 and h2 need to be declared and initialised to zero. max may not be
defined (this is a nuisance and one of the silly quirks of C, it's
easier all round to write the logic yourself).
There's a typo in p=> (should be p->). Ypu don't need to parenthesise
a return expression, though it doesn't do any harm except make the
code harder to read.

 

[Lew Pitcher]

I have come accross with the code for finding Depth of tree, i am
not
getting this, please anyone throw a light on this ....

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg


please explain in code level rather than theoratical level.


int depth(treenode *p)
{
if(p==NULL)return(0);
if(p->left){h1=depth(p->left);}
if(p=>right){h2=depth(p->right);}
return(max(h1,h2)+1);
}

Your treenode consists of some data (not shown) and two pointers. The left
pointer points to the node that starts the left branch of the tree below
the current node, and the right pointer points to the node that starts the
right branch of the tree below the current node. Either (or both) of these
pointers may be NULL, signifying that there are no branch nodes in that
direction below the current node.

The depth() function works on these pointers. You give it a pointer to a
node, and it counts the depth of the tree pointed to by that pointer.

If the pointer you give depth() is NULL, then there is no treenode, and
therefore no subtree. The depth of this branch is zero.

OTOH, if you gave depth() a non-null pointer, then that pointer points to
one level of depth, and the node at that level may lead to other levels of
depth. The code measures the depth of each branch from the current node,
and finds out which branch is longer. It then adds 1 (for the current node)
to that count, and returns that value as the depth of the tree /from this
node down/.

Since the function is recursive, it uses itself to determine the depths of
each branch of the current node.

 

[Ben Bacarisse]

I have come accross with the code for finding Depth of tree, i am
not
getting this, please anyone throw a light on this ....

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg

please explain in code level rather than theoratical level.

int depth(treenode *p)
{
if(p==NULL)return(0);
if(p->left){h1=depth(p->left);}
if(p=>right){h2=depth(p->right);}
return(max(h1,h2)+1);
}

Other people have explained. All I'd say is that this seem overly
complex. depth is happy to be passed NULL so you can just write:

if (p)
return max(depth(p->left), depth(p->right)) + 1;
else return 0;

In fact, I'd consider:

return p ? max(depth(p->left), depth(p->right)) + 1 : 0;

 

[Eric Sosman]

Other people have explained. All I'd say is that this seem overly
complex. depth is happy to be passed NULL so you can just write:

if (p)
return max(depth(p->left), depth(p->right)) + 1;
else return 0;

In fact, I'd consider:

return p ? max(depth(p->left), depth(p->right)) + 1 : 0;

You'd better hope `max' isn't the obvious macro

#define max(x,y) ( (x) > (y) ? (x) : (y) )

.... or you'll be doing quite a bit more computation than the
(corrected) original would.

Let's see: If I've counted correctly, this would use seventy-
six function calls to compute the depth of the O.P.'s nine-node
tree. "Efficiency" isn't a fashionable word nowadays, but ...

 

[Ben Pfaff]

In fact, I'd consider:

return p ? max(depth(p->left), depth(p->right)) + 1 : 0;

"max" is commonly used as an example of a macro that evaluates
its arguments more than once, e.g.:
#define max(x, y) ((x) > (y) ? (x) : (y))

I hope that in this case it would be implemented as a function.
Otherwise this "depth" function would waste a lot of CPU time.

 

[Eric Sosman]

You'd better hope `max' isn't the obvious macro

#define max(x,y) ( (x) > (y) ? (x) : (y) )

... or you'll be doing quite a bit more computation than the
(corrected) original would.

Let's see: If I've counted correctly, this would use seventy-
six function calls to compute the depth of the O.P.'s nine-node
tree. "Efficiency" isn't a fashionable word nowadays, but ...

Got interested; wrote a little program. Here's the number
of calls to explore complete binary trees of various depths:

Depth Calls
1 4
2 13
3 40
4 121
5 364
6 1093
7 3280
8 9841
9 29524
10 88573
11 265720
12 797161
13 2391484
14 7174453
15 21523360
16 64570081
17 193710244
18 581130733
19 1743392200
20 (> INT_MAX)

If I weren't lazy I'd try to solve the recursion and get an
exact formula. Instead, I took the easy way out, threw the numbers
into a spreadsheet, and did a logarithmic least-squares fit to
arrive at

calls ~= 2 ** (1.59 * depth + 0.53)

That is, each additional level approximately triples the number
of calls required to compute the depth (2**1.59 ~= 3.01).

Conclusion: Ben had *really* better hope max() isn't a macro!

 

[Ben Bacarisse]

"max" is commonly used as an example of a macro that evaluates
its arguments more than once, e.g.:
#define max(x, y) ((x) > (y) ? (x) : (y))

I hope that in this case it would be implemented as a function.
Otherwise this "depth" function would waste a lot of CPU time.

Good point. I'd like to think such a macro would be called MAX but it
is not always so. The OP (or Original Programmer since I don't think
the original poster wrote the code) may have known that max is a macro
and hence wrote the otherwise rather complex depth code.

I'd re-write max rather than the depth code!

 

[Ben Pfaff]

Got interested; wrote a little program. Here's the number
of calls to explore complete binary trees of various depths:

Depth Calls
1 4
2 13
3 40
4 121
5 364
6 1093
7 3280
8 9841
9 29524
10 88573
11 265720
12 797161
13 2391484
14 7174453
15 21523360
16 64570081
17 193710244
18 581130733
19 1743392200
20 (> INT_MAX)

If I weren't lazy I'd try to solve the recursion and get an
exact formula. Instead, I took the easy way out, threw the numbers
into a spreadsheet, and did a logarithmic least-squares fit to
arrive at

You can be lazy and still get an exact formula, by typing
"4,13,40,121,364" into the form here:
http://www.research.att.com/njas/sequences/

You end up here:
http://www.research.att.com/~njas/sequences/A003462

and the exact formula is therefore (from that page):
(3^n - 1)/2

 

[Ben Bacarisse]

On 3/11/2010 1:17 PM, Ben Bacarisse wrote:

You'd better hope `max' isn't the obvious macro

#define max(x,y) ( (x) > (y) ? (x) : (y) )

One would do more than hope; one would check!

To me, the obvious macro is 'MAX'. 'max' as a macro is, well, words
fail me, but you are right -- some people write that.

<snip>

 

[Ben Bacarisse]

Conclusion: Ben had *really* better hope max() isn't a macro!

Note to the OP, you can write:

return p ? (max)(depth(p->left), depth(p->right)) + 1 : 0;

so as to be sure. Your compiler will now tell you if there is no max
function.

Note to self: Always use this style when posting to Usenet

 

[Eric Sosman]

[...]
If I weren't lazy I'd try to solve the recursion and get an
exact formula. Instead, I took the easy way out, threw the numbers
into a spreadsheet, and did a logarithmic least-squares fit to
arrive at

You can be lazy and still get an exact formula, by typing
"4,13,40,121,364" into the form here:
http://www.research.att.com/njas/sequences/

Neat resource! My bookmark file thanks you!

Of course, a true mathematician would have concluded "by
inspection" that the number of calls to explore the complete
tree of depth n is the same as the number of non-degenerate
right-angled incongruent integer-edged Heron triangles whose
circumdiameter is the product of n distinct primes of shape
4k + 1. (Slaps forehead: Now, why didn't *I* think of that?)

 

[BruceS]

[...]
     If I weren't lazy I'd try to solve the recursion and get an
exact formula.  Instead, I took the easy way out, threw the numbers
into a spreadsheet, and did a logarithmic least-squares fit to
arrive at

You can be lazy and still get an exact formula, by typing
"4,13,40,121,364" into the form here:
         http://www.research.att.com/njas/sequences/

     Neat resource!  My bookmark file thanks you!

<snip>

Mine as well. Thanks Ben. This could really come in handy.

 

[Nick Keighley]

     Of course, a true mathematician would have concluded "by
inspection" that the number of calls to explore the complete
tree of depth n is the same as the number of non-degenerate
right-angled incongruent integer-edged Heron triangles whose
circumdiameter is the product of n distinct primes of shape
4k + 1.  (Slaps forehead: Now, why didn't *I* think of that?)

I knew a programmer who dealt with mathematicians ("tame
mathematicians" he referred to them as) on a regular basis; he came to
the conclusion that any mathematical question asked of them always
gave one of these standard answers:-

1. I don't understand why you cannot see that this follows trivially
from the axioms.
2. this is a hard problem to which we currently don't have a solution

 

[Giovanni Senatore]

I have come accross with the code for finding Depth of tree, i am
not
getting this, please anyone throw a light on this ....

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg


please explain in code level rather than theoratical level.


int depth(treenode *p)
{
if(p==NULL)return(0);
if(p->left){h1=depth(p->left);}
if(p=>right){h2=depth(p->right);}
return(max(h1,h2)+1);


}

i think that something like this can be functional...

#define MAX(A,B) (A>B)?A:B

typedef struct node {
void* value; /* pointer to some value */
struct node* l; /* left side pointer */
struct node* r; /* right side pointer */
} node_t;

/*
* globally declared var just to avoid passing as
* argument....
*/
int curdepth; /* current depth counter, it could start
* from 0 or 1 as needed
*/
int maxdepth; /* max depth counter, same as curdepth */

void
tree(node_t* node)
{
curdepth++; /* update current position */
if(node->l != NULL) tree(node->l); /* follow left side if any */
if(node->r != NULL) tree(node->r); /* follow right side if any */
/*
* if and only if this is the the last node of the graph tree
* i must compute the max value between curdepth and
* the previous maxdepth.
*/
maxdepth=MAX(maxdepth,curdepth);
curdepth--; /* since i go back to the
parent i need to decrease
the current position counter
before return */
return;
}

 

[Eric Sosman]

I knew a programmer who dealt with mathematicians ("tame
mathematicians" he referred to them as) on a regular basis; he came to
the conclusion that any mathematical question asked of them always
gave one of these standard answers:-

1. I don't understand why you cannot see that this follows trivially
from the axioms.
2. this is a hard problem to which we currently don't have a solution

Martin "Mathematical Games" Gardner wrote of relating a
mathematical problem to an actual mathematician:

A few years ago I had the pleasure of explaining
[Scott Kim's] polycube-snake problem to John Horton
Conway, the Cambridge mathematician. When I concluded
by saying Kim had not yet shown that two snakes could
not tile three-dimensional space, Conway instantly
said, "But it's obvious that--" He checked himself in
mid-sentence, stared into three-space for a minute or
two, then exclaimed, "It's *not* obvious!"

 

[Andrew Poelstra]

i think that something like this can be functional...

#define MAX(A,B) (A>B)?A:B

typedef struct node {
void* value; /* pointer to some value */
struct node* l; /* left side pointer */
struct node* r; /* right side pointer */
} node_t;

/*
* globally declared var just to avoid passing as
* argument....
*/
int curdepth; /* current depth counter, it could start
* from 0 or 1 as needed
*/
int maxdepth; /* max depth counter, same as curdepth */

void
tree(node_t* node)
{
curdepth++; /* update current position */
if(node->l != NULL) tree(node->l); /* follow left side if any */
if(node->r != NULL) tree(node->r); /* follow right side if any */
/*
* if and only if this is the the last node of the graph tree
* i must compute the max value between curdepth and
* the previous maxdepth.
*/
maxdepth=MAX(maxdepth,curdepth);
curdepth--; /* since i go back to the
parent i need to decrease
the current position counter
before return */
return;
}

/Don't/ do that. This solution obviously cannot work for
more than one call, and after an absurd amount of effort
analysing it, I'm pretty sure it won't even work once.

At least, it can't return anything since it returns void
and its side effect *shudder* is cancelled at the end of
each call.

The original function was correct - and could be seen to
be so at first glance.

 

[Phred Phungus]

I knew a programmer who dealt with mathematicians ("tame
mathematicians" he referred to them as) on a regular basis; he came to
the conclusion that any mathematical question asked of them always
gave one of these standard answers:-

1. I don't understand why you cannot see that this follows trivially
from the axioms.
2. this is a hard problem to which we currently don't have a solution

Martin "Mathematical Games" Gardner wrote of relating a
mathematical problem to an actual mathematician:

A few years ago I had the pleasure of explaining
[Scott Kim's] polycube-snake problem to John Horton
Conway, the Cambridge mathematician. When I concluded
by saying Kim had not yet shown that two snakes could
not tile three-dimensional space, Conway instantly
said, "But it's obvious that--" He checked himself in
mid-sentence, stared into three-space for a minute or
two, then exclaimed, "It's *not* obvious!"

Conway and Sloane are legends in the theory of lattices. You'd think
such persons would be all about using computers, but it's not the case
at least half the time. For instance, Griess calculated the order the
Monster ~10^56 by hand. I believe Conway is said to have a series of
daunting mental math calculations that he uses as part of the security
to his log-in.

 

[Phred Phungus]

[...]
If I weren't lazy I'd try to solve the recursion and get an
exact formula. Instead, I took the easy way out, threw the numbers
into a spreadsheet, and did a logarithmic least-squares fit to
arrive at
You can be lazy and still get an exact formula, by typing
"4,13,40,121,364" into the form here:
http://www.research.att.com/njas/sequences/

Neat resource! My bookmark file thanks you!

<snip>

Mine as well. Thanks Ben. This could really come in handy.

It's a great resource. If you can't figure out what the general rule is
for an integer sequence, calculate the first 5 terms and chances are
you'll get a match.

It's not much, but I've got my own entry there in immortality:
http://www.research.att.com/~njas/sequences/A084386

Dr. Sloane fully intends this resource to outlast us all.