Solved

height of binary tree

Posted on 2002-05-01
6
3,236 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
Comment Utility
It's agaisnt EE policy to do homework questions.
0
 
LVL 4

Expert Comment

by:ct.smith
Comment Utility
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
Comment Utility
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
Comprehensive Backup Solutions for Microsoft

Acronis protects the complete Microsoft technology stack: Windows Server, Windows PC, laptop and Surface data; Microsoft business applications; Microsoft Hyper-V; Azure VMs; Microsoft Windows Server 2016; Microsoft Exchange 2016 and SQL Server 2016.

 
LVL 4

Expert Comment

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

Expert Comment

by:vrelhan
Comment Utility
You can see C++ code thro book

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

Expert Comment

by:CreepGin
Comment Utility
"return 0;"

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

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

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.

743 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

16 Experts available now in Live!

Get 1:1 Help Now