Depth of Binary Tree
RAKHE
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
> {
> if(p==NULL)return(0);
> if(p->left){h1=depth(p->left);}
> if(p=>right){h2=depth(p->right);}
> return(max(h1,h2)+1);
>
>
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
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.
--
Lew Pitcher
Master Codewright & JOAT-in-training | Registered Linux User #112576
Me: http://pitcher.digitalfreehold.ca/ | Just Linux: http://justlinux.ca/
---------- Slackware - Because I know what I'm doing. ------
Ben Bacarisse
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;
--
Ben.
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 ...
--
Eric Sosman
eso...@ieee-dot-org.invalid
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.
--
"Welcome to the wonderful world of undefined behavior, where the demons
are nasal and the DeathStation users are nervous." --Daniel Fox
Eric Sosman
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!
--
Eric Sosman
eso...@ieee-dot-org.invalid
Ben Bacarisse
> Ben Bacarisse <ben.u...@bsb.me.uk> writes:
>
>> 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.
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.
Ben Pfaff
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
--
"Given that computing power increases exponentially with time,
algorithms with exponential or better O-notations
are actually linear with a large constant."
--Mike Lee
Ben Bacarisse
> On 3/11/2010 1:17 PM, Ben Bacarisse wrote:
<snip>
>> 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) )
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.
Ben Bacarisse
<snip>
> 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 :-)
--
Ben.
Eric Sosman
> Eric Sosman<eso...@ieee-dot-org.invalid> writes:
>> [...]
>> 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?)
--
Eric Sosman
eso...@ieee-dot-org.invalid
BruceS
> On 3/11/2010 4:26 PM, Ben Pfaff wrote:
>
> >> [...]
> >> 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!
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 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
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!"
--
Eric Sosman
eso...@ieee-dot-org.invalid
Andrew Poelstra
/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.
--
Andrew Poelstra
http://www.wpsoftware.net/andrew
Michal Nazarewicz
>> Conclusion: Ben had *really* better hope max() isn't a macro!
Ben Bacarisse <ben.u...@bsb.me.uk> writes:
> 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.
However some compilers may have extensions which allow to define macro
in a way that arguments are evaluated only once. In particular if I'm
not mistaken the following is valid GCC macro:
#define max(x, y) ({ \
const typeof(x) _x = (x); \
const typeof(y) _y = (y); \
_x > _y ? _x : _y; \
})
--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>--<jid:mina86*jabber.org>--ooO--(_)--Ooo--
Phred Phungus
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.
--
fred
Phred Phungus
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.
--
fred