Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Calculating height of a Binary Tree :) Check if a tree is balanced or not :)
Diff in left and right height should be less than or equal to 1.
int traverse(node){
if(node == null)
return 0;
int leftHeight = traverse(node->left);
int rightHeight = traverse(node->right);
isBalanced(leftHeight,rightHeight,node);
return max(leftHeight,rightHeight) + 1;
}
void isBalanced(int left,int right,node){
int diff = |left - right|;
if(diff > 1)
{ un-balanced at node}
else
{ balanced }
}
/////////////////////EXAMPLE//////////////////
a
/ \
b c
/ \ / \
d e f i
/ \
g h
The tree above is balanced ( don't believe me, dry run it once )
//////////////EXAMPLE/////////////////////
a
/ \
b c
/ \ / \
d e f i
/ \
g h
/
j
This tree is un-balanced at `c` ... Why ???? because it left height is 3 and it's right height is 1
What is Height of a tree ????
Height is measured in upward direction. The longest path from leaf to the root is called height of a tree.
Height of leaf node is 1
int traverse(node){
if(node == null)
return 0;
int leftHeight = traverse(node->left);
int rightHeight = traverse(node->right);
int height = max(leftHeight,rightHeight) + 1;
return height;
}
///////////EXAMPLE TREE////////////////// (because i need one every time :P )
a
/ \
b c
/ \ / \
d e f i
/ \
g h
from above function we get Height of tree as 4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.