Solved

height of binary tree

Posted on 2002-05-01
6
3,249 Views
Last Modified: 2013-11-15
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
Comment
Question by:annihilator
6 Comments
 
LVL 30

Expert Comment

by:Axter
ID: 6984082
It's agaisnt EE policy to do homework questions.
0
 
LVL 4

Expert Comment

by:ct.smith
ID: 6984104
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

by:
frechter earned 50 total points
ID: 6985434
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
Complete VMware vSphere® ESX(i) & Hyper-V Backup

Capture your entire system, including the host, with patented disk imaging integrated with VMware VADP / Microsoft VSS and RCT. RTOs is as low as 15 seconds with Acronis Active Restore™. You can enjoy unlimited P2V/V2V migrations from any source (even from a different hypervisor)

 
LVL 4

Expert Comment

by:ct.smith
ID: 6987835
Hey frechter, you may want to look over the EE homework policy!
0
 

Expert Comment

by:vrelhan
ID: 6987938
You can see C++ code thro book

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

Expert Comment

by:CreepGin
ID: 21434327
"return 0;"

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

Featured Post

U.S. Department of Agriculture and Acronis Access

With the new era of mobile computing, smartphones and tablets, wireless communications and cloud services, the USDA sought to take advantage of a mobilized workforce and the blurring lines between personal and corporate computing resources.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Workplace bullying has increased with the use of email and social media. Retain evidence of this with email archiving to protect your employees.
Skype is a P2P (Peer to Peer) instant messaging and VOIP (Voice over IP) service – as well as a whole lot more.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question