Problem Explanation

We are given a binary tree, and we need to check if it is height-balanced. A binary tree is height-balanced if the depths of the two subtrees of every node never differ by more than one (including the root node).

The depth of a binary tree is the number of nodes from the root node to the deepest leaf node. Simply put, this problem is asking us to ensure that, for every node in the tree, the difference in depth between its left subtree and right subtree is not more than 1.

Walkthrough

Let's walk through the first example.

Given the binary tree:

1
2
3    3
4   / \
5  9  20
6    /  \
7   15   7

The maximum depth of the left subtree (rooted at 9) is 1, and the maximum depth of the right subtree (rooted at 20) is 2. The absolute difference is 1, which is equal to or less than 1. We then recursively check the balance for its left subtree and right subtree as well. Both left and right subtrees also satisfy the balanced condition. Therefore, this binary tree is balanced.

Solution Approach

The solution uses a recursive depth-first search approach. The maxDepth function calculates the depth of a given node.

For each node, the algorithm calculates the depth of the left and right subtrees, checks the difference, and then recursively checks the balance of the left and right subtrees.

For the recursion base case, when the node is null, the tree is balanced (return true), and its depth is 0.

Python Solution

1
2python
3class Solution:
4    def isBalanced(self, root):
5        if root is None:
6            return True
7        leftDepth = self.maxDepth(root.left)
8        rightDepth = self.maxDepth(root.right)
9        return abs(leftDepth - rightDepth) <= 1 and \
10               self.isBalanced(root.left) and self.isBalanced(root.right)
11
12    def maxDepth(self, root):
13        if root is None:
14            return 0
15        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Java Solution

1
2java
3class Solution {
4    public boolean isBalanced(TreeNode root) {
5        if (root == null) {
6            return true;
7        }
8        int leftDepth = maxDepth(root.left);
9        int rightDepth = maxDepth(root.right);
10        return Math.abs(leftDepth - rightDepth) <= 1 &&
11               isBalanced(root.left) &&
12               isBalanced(root.right);
13    }
14
15    private int maxDepth(TreeNode root) {
16        if (root == null) {
17            return 0;
18        }
19        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
20    }
21}

JavaScript Solution

1
2javascript
3class Solution {
4    isBalanced(root) {
5        if (!root) {
6            return true;
7        }
8        let leftDepth = this.maxDepth(root.left);
9        let rightDepth = this.maxDepth(root.right);
10        return Math.abs(leftDepth - rightDepth) <= 1 &&
11               this.isBalanced(root.left) &&
12               this.isBalanced(root.right);
13    }
14
15    maxDepth(root) {
16        if (!root) {
17            return 0;
18        }
19        return 1 + Math.max(this.maxDepth(root.left), this.maxDepth(root.right));
20    }
21}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool isBalanced(TreeNode* root) {
6        if (!root) {
7            return true;
8        }
9        int leftDepth = maxDepth(root->left);
10        int rightDepth = maxDepth(root->right);
11        return abs(leftDepth - rightDepth) <= 1 &&
12               isBalanced(root->left) &&
13               isBalanced(root->right);
14    }
15
16private:
17    int maxDepth(TreeNode* root) {
18        if (!root) {
19            return 0;
20        }
21        return 1 + max(maxDepth(root->left), maxDepth(root->right));
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsBalanced(TreeNode root) {
5        if (root == null) {
6            return true;
7        }
8        int leftDepth = MaxDepth(root.left);
9        int rightDepth = MaxDepth(root.right);
10        return Math.Abs(leftDepth - rightDepth) <= 1 &&
11               IsBalanced(root.left) &&
12               IsBalanced(root.right);
13    }
14
15    private int MaxDepth(TreeNode root) {
16        if (root == null) {
17            return 0;
18        }
19        return 1 + Math.Max(MaxDepth(root.left), MaxDepth(root.right));
20    }
21}

In each language, we have a helper function maxDepth(TreeNode *node) which computes the maximum depth of a node recursively. Besides that, we have the main isBalanced function, which calls maxDepth for the left and right children of each node and checks the difference of both depths to ensure it is at most 1. The recursion ends when a node is null, returning it as balanced (since a null tree is height-balanced).# Ruby Solution

1
2ruby
3class Solution
4    def is_balanced(root)
5        return true if root.nil?
6        
7        left_depth = max_depth(root.left)
8        right_depth = max_depth(root.right)
9        
10        return (left_depth - right_depth).abs <= 1 &&
11               is_balanced(root.left) &&
12               is_balanced(root.right)
13    end
14
15    def max_depth(root)
16        return 0 if root.nil?
17        
18        return 1 + [max_depth(root.left), max_depth(root.right)].max
19    end
20end

Golang Solution

1
2golang
3type Solution struct {}
4
5func (s *Solution) isBalanced(root *TreeNode) bool {
6    if root == nil {
7        return true
8    }
9    
10    leftDepth := s.maxDepth(root.Left)
11    rightDepth := s.maxDepth(root.Right)
12    
13    return abs(leftDepth - rightDepth) <= 1 &&
14           s.isBalanced(root.Left) &&
15           s.isBalanced(root.Right)
16}
17
18func (s *Solution) maxDepth(root *TreeNode) int {
19    if root == nil {
20        return 0
21    }
22    
23    return 1 + max(s.maxDepth(root.Left), s.maxDepth(root.Right))
24}
25
26func abs(n int) int {
27    if n < 0 {
28        return -n
29    }
30    return n
31}
32
33func max(a, b int) int {
34    if a > b {
35        return a
36    }
37    return b
38}

In above solutions for Ruby and Golang, we first check if the root is null, if yes we return true as a null tree is considered balanced. If root is not null, we calculate the depth of the right and left subtree calling max_depth() recursively. We then check, if the absolute difference between the depths of right and left subtree is less than or equal to 1 and, if both right and left subtrees are also balanced. If the conditions meet, we return true indicating the tree is balanced, else the tree is not balanced and we return false.

The helper function max_depth(node) is written to compute the maximum depth of a node. it calls itself recursively.