EMChamp Blog

Coding Problem 8 | Check if binary tree is balanced

I was not sure how to approach this one either until I took a look at the solutions discussion at leetcode and saw that people were calculating the depth. I actually had never seen recursion used in this way but it made sense since we can leverage what we already had by counting the depth of subtrees to determine if the trees were balanced. This solution seems fairly inefficient since for every node we have to calculate the depth of the subtree, there might be better ones out there on the forum.

1) If root is empty, tree is defintely balanced.

2) Calculate depth of current node left subtree and right subtree using

1
2
3

(Math.abs(depth(root.left) - depth(root.right)) > 1)

once you get this part it is downhill. If the tree is imbalanced return false. Otherwise recursively continue down the nodes left and right subtree with this

1
2
3

(isBalanced(root.left) && isBalanced(root.right))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null)
return true;

if(Math.abs(depth(root.left) - depth(root.right)) > 1)
return false;
else
return (isBalanced(root.left) && isBalanced(root.right));
}


public int depth(TreeNode root) {
if(root==null)
return 0;

if(root.left != null || root.right != null)
return Math.max(depth(root.left),depth(root.right))+1;
else
return 1;
}
}