Is binary tree balanced

© Parineeth M R

Question 15. Find if a binary tree is balanced


A binary tree is balanced if at every node in the tree, the absolute difference between the height of the left-subtree and the height of the right sub-tree doesn’t exceed 1. To solve the problem we recursively traverse the tree and calculate the height of the nodes in a bottom up manner. If at any node, the difference between the height of the left and right sub-trees exceeds 1, we report that the tree is unbalanced.

C/C++


/*cur_node: node of the binary tree being checked
height: height of the current node is returned here
Return value: 1 if the tree is balanced, 0 otherwise
*/
int is_balanced(struct node *cur_node, int *height)
{
	int is_left_balanced, is_right_balanced;
	int left_height, right_height;

	if (!cur_node) {
		*height = 0;
		return 1;
	}

	is_left_balanced = is_balanced(cur_node->left, &left_height);
	is_right_balanced = is_balanced(cur_node->right, &right_height);

	if (!is_left_balanced || !is_right_balanced)
		return 0;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (abs(left_height - right_height) > 1)
		return 0;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	*height = max(left_height, right_height) + 1;

	return 1;	
}



Java


/*curNode: node of the binary tree being checked
height: height of the curNode is returned here
Return value: true if the tree is balanced, false otherwise
*/
public static boolean isBalanced(TreeNode curNode, Int height) {
	Int leftHeight = new Int();
	Int rightHeight = new Int();

	if (curNode == null) {
		height.value = 0;
		return true;
	}


	boolean isLeftBalanced = isBalanced(curNode.left, leftHeight);
	boolean isRightBalanced = isBalanced(curNode.right, rightHeight);

	if (!isLeftBalanced || !isRightBalanced)
		return false;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (Math.abs(leftHeight.value - rightHeight.value) > 1)
		return false;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	height.value = Math.max(leftHeight.value, rightHeight.value) + 1;

	return true;	
}



Python


#cur_node: node of the binary tree being checked
#Return values: 1. True if the tree is balanced, False otherwise
#		2. height of the cur_node is also returned
@staticmethod
def is_balanced(cur_node) :
	if (not cur_node) :
		height = 0
		return True, height
	
	is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
	is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

	#To get the height of the current node, we find the maximum of the  
	#left subtree height and the right subtree height and add 1 to it
	height = max(left_height, right_height) + 1

	if (not is_left_balanced or not is_right_balanced):
		return False, height

	#If the difference between height of left subtree and height of
	#right subtree is more than 1, then the tree is unbalanced
	if (abs(left_height - right_height) > 1):
		return False, height
	
	return True, height