Solved

# height of binary tree

Posted on 2002-05-01
3,236 Views
hello
i have to find the height of binary tree....which is
height of binary tree=log2n +1
but i want some code in c++ to find the height .....
0
Question by:annihilator

LVL 30

Expert Comment

It's agaisnt EE policy to do homework questions.
0

LVL 4

Expert Comment

log n + 1 is NOT the height of a binary tree, it is only the minimum height.  The height is only lob n + 1 when the tree is balanced.

I use to see that mistake all the time when I taught this stuff, so I feel obligated to pick on it.

Anyways, there are two approaches you can take.  If you've tracked the number of nodes in the tree, then you can just run the formula you stated.  The other method is to use the first segment of a depth-first traversal.
0

LVL 2

Accepted Solution

frechter earned 50 total points
this is a recursive c (or c++) function:

int height(node * p_root) {
if (p_root) {
//fing the height of the left and right sons
int left_height = height(p_root->left);
int right_height = height(p_root->right);

//return the max height (max(left,right))
if (left_height>right_height) return  left_height+1;
else reutrn right_height+1;

} else  return 0; //if this is the bottom  of the tree

}

0

LVL 4

Expert Comment

Hey frechter, you may want to look over the EE homework policy!
0

Expert Comment

You can see C++ code thro book

Data Structures using C and C++ by Tannenbaum.
0

Expert Comment

"return 0;"

in most cases, it should be "return -1;"
0

## Featured Post

I use more than 1 computer in my office for various reasons. Multiple keyboards and mice take up more than just extra space, they make working a little more complicated. Using one mouse and keyboard for all of my computers makes life easier. This co…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
This video will demonstrate how to find the puppet warp tool from the edit menu and where to put the points to edit.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.