Solved

height of binary tree

Posted on 2002-05-01
6
3,244 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
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.

 
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Disk Wipe Utility 6 83
Desktop clocks and date, gone forever? 10 122
What would cause Wake On LAN to stop functioning all of a sudden? 8 75
Least Squares Curve Fitting 4 61
A high-level exploration of how our ever-increasing access to information has changed the way we do our jobs.
All of the resources available today make learning a new digital media easier than ever-- if you know where to begin. This is a clear, simple guide to a few of the basic digital art mediums and how to begin learning them on your own.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

920 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now