Balanced binary tree

What is a balanced binary tree?  A tree is balanced when difference between height of left subtree and right subtree at every node is not more than one. Problem is to check if given binary tree is balanced tree? For example, below tree is balanced tree because at all nodes difference between height of left and right subtree is not more than 1.

balanced binary tree

However, below tree is not balanced as difference between height of left subtree and right subtree at node(10) is 2.

Balanced binary tree : Thoughts

One thing to notice very carefully, that for a tree to be balanced, every subtree at each node should be balanced too. It cannot be balanced if it is balanced at root node.

As solution to original tree depends on subtree, we have to find first if subtrees are balanced. If yes, then compare the height of left subtree and right subtree, if difference is less than or equal to 1, return true. Refer Height of binary tree to learn how to find height of binary tree.

Let’s see how does it work with an example. Given below binary tree and see how we can figure out if it is balanced or not?

Start with root node which is node(10). Height of left subtree is 4 and right subtree is 3. Difference of heights is 1, now we have to check if it’s left and right subtrees are balanced?

At node(5), again height difference is 1, so we will go down left and right subtrees and check if they are balanced.

At node(1), it’s leaf node and hence, it must be balanced. So we return true to parent node(5).

Now, we have to check if right subtree of node(5) is balanced too? We move down right subtree and go all the way to node(6), which is leaf node, which returns true to node(8). Also, node(9) will return true. At node(8), both left and right subtree have returned true, we should return true from node(8) too.

At node(5), left and subtree have returned true and we know that difference between height of left and right subtree is only 1. Hence we will return true from node(5) too.

Next, we have to check if right subtree of node(10) is balanced too.

Left and right subtree of node(19) are leaf nodes, hence both will return true.

At node(19), left and right subtree has returned true and height difference is zero, hence it will return true to parent node.

Now, at last, we have received that left and right subtrees are balanced at node(10) and height difference is 1, hence, entire tree is balanced.

Balanced binary tree : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

#define true 1
#define false 0
#define MAX(a,b)  (a < b ? b : a)

Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	
	return newNode;
}
Node *addNode(Node *node, int value){
	if(!node)
		return createNode(value);
    
	if (node->value > value)
		node->left = addNode(node->left, value);
	else
		node->right = addNode(node->right, value);
		
	return node;
}

int height( Node *root){
	if( !root ) 
		return 0;
	
	int lheight = height( root->left);
	int rheight = height( root->right);
	
	return 1 + MAX (lheight, rheight );
}

int isHeightBalanced( Node * root ){
	if(!root) return true;
	
	int lheight = height( root->left );
	int rheight = height( root->right );
	
	return (abs( lheight-rheight) <= 1 )
		   && isHeightBalanced( root->left )
		   && isHeightBalanced( root->right );
	
}
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
    
	//Creating a binary tree
	root = addNode(root, 30);
	root = addNode(root, 20);
	root = addNode(root, 15);
	root = addNode(root, 25);
	root = addNode(root, 40);
	root = addNode(root, 38);
	root = addNode(root, 39);
	root = addNode(root, 45);
	root = addNode(root, 47);
	root = addNode(root, 49);
    
	printf( "Is tree height balanced : %s", 
		isHeightBalanced( root ) ? "Yes" : "No" );
	
	return 0;
}

Complexity of algorithm to find if tree is balanced or not is O(n) as we will be scanning all nodes at least once. However, if you notice that we are scanning tree multiple times when calculating height of left and subtree at every node. How can we avoid these repeated scans?

As we are already scanning all nodes, can we pass the two things from subtree to root node? If we can pass from subtree if subtree is balanced or not and then what is height of subtree. Idea is to bump height all the way to root node and use that height to check if tree at root is balanced or not.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

#define true 1
#define false 0
#define MAX(a,b)  (a < b ? b : a)

Node *createNode(int value){
	Node * newNode =  (Node *)malloc(sizeof(Node));
	newNode->value = value;
	newNode->right= NULL;
	newNode->left = NULL;
	
	return newNode;
}
Node *addNode(Node *node, int value){
	if(!node)
		return createNode(value);
    
	if (node->value > value)
		node->left = addNode(node->left, value);
	else
		node->right = addNode(node->right, value);
		
	return node;
}

int isHeightBalanced( Node * root, int *height ){
	if(!root){
		*height = 0;
		return true;	
	} 
	
	int lheight = 0, rheight = 0;
	int lBalanced = isHeightBalanced( root->left, &lheight );
	int rBalanced = isHeightBalanced( root->right, & rheight );
	
	//Update the height
	*height = 1 + MAX ( lheight, rheight);
	
	//Check if difference between two height is more than 1
	if (abs( lheight-rheight) > 1 ) return false;
	
	return lBalanced && rBalanced;
		  
}
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
    
	//Creating a binary tree
	root = addNode(root, 30);
	root = addNode(root, 20);
	root = addNode(root, 15);
	root = addNode(root, 25);
	root = addNode(root, 40);
	root = addNode(root, 38);
	root = addNode(root, 39);
	root = addNode(root, 45);
	root = addNode(root, 47);
	root = addNode(root, 49);
    
	printf( "Is tree height balanced : %s", 
		isHeightBalanced( root ) ? "Yes" : "No" );
	
	return 0;
}

Complexity of this implementation is also O(n) however, number of scans of each node is only once.

Please share if there is something is wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com