© 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