Determine if BinaryTree is Balanced
This post will explore the problem of checking whether a binary tree is balanced or not. A binary tree is considered to be balanced if the height difference between two subtrees is no more than 1. This definition could be different depending on use cases. We will explore two approaches to this problem. One where all nodes are visited whereas the second approach takes advantage of early termination if one subtree is unbalanced.
Brute Force
The brute force approach will recursively visit every node using in-order traversal. For each node, the algorithm will get the height of its left subtree and right subtree. The greater height of the two is incremented by one, and is returned to the parent of the current node where the process repeats. The difference is computed one last time at the root and returns false if it is larger than one.
Implementation
public static boolean isBalanced(TreeNode root) {
if (root == null)
return true;
int leftHeight = treeHeight(root.left);
int rightHeight = treeHeight(root.right);
return Math.abs(leftHeight - rightHeight) <= 1;
}Helper Method
private static int treeHeight(TreeNode root) {
if (root == null)
return 0;
int leftHeight = treeHeight(root.left);
int rightHeight = treeHeight(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}Optimized
The optimized solution takes advantage of early termination in the event where one of the subtrees is detected to be unbalanced. When this occurs, the unbalanced status is passed to the parent and eventually the root. At the point where the unbalanced status is detected, there is no need to check for any other subtree.
TreeNodeAttributes Definition
public static class TreeNodeAttributes {
boolean isBalanced;
int height;
public TreeNodeAttributes(isBalanced, height) {
isBalanced = isBalanced;
height = height;
}
}Implementation
public static boolean isBalanced(TreeNode root) {
return getAttributes(root).isBalanced;
}Helper Method
public static TreeNodeAttributes getAttributes(TreeNode root) {
if (root == null)
return new TreeNodeAttributes(true, 0);
TreeNodeAttributes leftAttr = getAttributes(root.left);
if (!leftAttr.isBalanced)
return leftAttr;
TreeNodeAttributes rightAttr = getAttributes(root.right);
if (!rightAttr.isBalanced)
return rightAttr;
TreeNodeAttributes curAttributes = new TreeNodeAttributes();
curAttributes.height = Math.max(leftAttr.height, rightAttr.height) + 1;
curAttributes.isBalanced = Math.abs(leftAttr.height - rightAttr.height) <= 1;
return curAttributes;
}