Solved

height of binary tree

Posted on 2002-05-01
6
3,251 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
Ransomware: The New Cyber Threat & How to Stop It

This infographic explains ransomware, type of malware that blocks access to your files or your systems and holds them hostage until a ransom is paid. It also examines the different types of ransomware and explains what you can do to thwart this sinister online threat.  

 
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

Ransomware: The New Cyber Threat & How to Stop It

This infographic explains ransomware, type of malware that blocks access to your files or your systems and holds them hostage until a ransom is paid. It also examines the different types of ransomware and explains what you can do to thwart this sinister online threat.  

Question has a verified solution.

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

Healthcare organizations in the United States must adhere to the guidance of both the HIPAA (Health Insurance Portability and Accountability Act) and HITECH (Health Information Technology for Economic and Clinical Health Act) for securing and protec…
This guide will walk you through the essential considerations and tech stack for building scalable websites. Know how to grow your business the smart way!
The viewer will learn how to successfully create a multiboot device using the SARDU utility on Windows 7. Start the SARDU utility: Change the image directory to wherever you store your ISOs, this will prevent you from having 2 copies of an ISO wit…
This is used to tweak the memory usage for your computer, it is used for servers more so than workstations but just be careful editing registry settings as it may cause irreversible results. I hold no responsibility for anything you do to the regist…

856 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