#### Archived

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

# binary search trees

This topic is 5900 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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?

Count

##### 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 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 on other sites
Have each node store its height, and maintain that across rotations and whatnot.

##### 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 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   eyou 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 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 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633679
• Total Posts
3013301
×