Archived

This topic is now archived and is closed to further replies.

yoda5

binary search trees

Recommended Posts

I was wondering if anyone might know a good way to find the height of each node of a binary tree...I have a program that does everything but that...it is supposed to list the total number of nodes(which it does) then the height of each node. Anyone have any ideas?

Share this post


Link to post
Share on other sites
use a recursive function, which takes a node and the height of that node. If the node is a leaf, it prints the passed height. If not, it recursively calls each of its children, with height+1 as the height parameter.


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
If speed is of the essence, then use a stack based approach, and simply watch the depth of the stack (= the value of the stack pointer).

Ciao, ¡muh!

Share this post


Link to post
Share on other sites
use a recursive function, which takes a node and the height of that node. If the node is a leaf, it prints the passed height. If not, it recursively calls each of its children, with height+1 as the height parameter.

Wouldn''t that cause the height to be too great because if the node has 2 children then the height would get incremented twice when the height is actually only 1.

Share this post


Link to post
Share on other sites
quote:
Original post by yoda5
use a recursive function, which takes a node and the height of that node. If the node is a leaf, it prints the passed height. If not, it recursively calls each of its children, with height+1 as the height parameter.

Wouldn''t that cause the height to be too great because if the node has 2 children then the height would get incremented twice when the height is actually only 1.

No. The height is passed by value, and is only incremented for the recursive call. So if you have this tree:

a
/ \
b c
/ \
d e

you have this sequence of calls:
a.height(0)
b.height(0+1)
d.height(1+1)
// prints "d has height 2"
e.height(1+1)
// prints "e has height 2"
c.height(0+1)
// prints "c has height 1"

See?


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
Well, if speed is of the essence, then store the height as you go down the tree into each node... then you can get O(1) time to find the height... simply query the height param of that node.

Share this post


Link to post
Share on other sites
quote:
Original post by Draigan
Well, if speed is of the essence, then store the height as you go down the tree into each node... then you can get O(1) time to find the height... simply query the height param of that node.


That only speeds things up if you intend to access the height multiple times, and if the accessor doesn''t intend to cache the height itself.


Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites