Balanced Binary Tree

LeetCode 110: Balanced Binary Tree Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a bottom-up Depth-First Search (DFS) to calculate the height of each subtree while simultaneously validating the balance constraint, returning a sentinel value (e.g., -1) immediately upon detecting an imbalance.

In the LeetCode 110 problem, we are asked to determine if a binary tree is height-balanced. A binary tree is considered height-balanced if, for every node in the tree, the height difference between its left and right subtrees is no more than 1. This definition applies recursively; not only must the root satisfy this condition, but every single node within the tree must also satisfy it.

This is a classic interview question that tests your ability to optimize tree traversals. While a naive solution is intuitive, the optimal Balanced Binary Tree solution requires understanding how to propagate information up from the leaves to the root efficiently.

Brute Force Approach for Balanced Binary Tree

The most straightforward way to solve this problem is to translate the definition directly into code using a top-down approach. For every node, we calculate the height of its left child and the height of its right child, check the difference, and then recursively repeat the process for the children.

Naive Logic

1. Define a helper function getHeight(node) that traverses down to the leaves to calculate the height of a specific node.
2. In the main isBalanced(node) function:
   • Calculate leftHeight = getHeight(node.left).
   • Calculate rightHeight = getHeight(node.right).
   • If abs(leftHeight - rightHeight) > 1, return false.
   • Otherwise, return isBalanced(node.left) && isBalanced(node.right).

Pseudo-code

function getHeight(node):
    if node is null: return 0
    return max(getHeight(node.left), getHeight(node.right)) + 1

function isBalanced(node):
    if node is null: return true
    if abs(getHeight(node.left) - getHeight(node.right)) > 1:
        return false
    return isBalanced(node.left) AND isBalanced(node.right)

Why this fails (Efficiency)

The time complexity of this approach is $O(N^2)$ in the worst case (a skewed tree). This occurs because getHeight is called repeatedly for the same nodes. For a node at depth $k$, getHeight visits it $k$ times (once for each ancestor's check). While this might pass the constraint of 5000 nodes, it is computationally redundant and demonstrates a lack of understanding regarding efficient tree traversals.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

We implement a helper function (often named dfs or checkHeight) that performs the postorder traversal.

1. Base Case: If the current node is null, its height is 0. This is a balanced state.
2. Recursive Step (Left): Recursively call the function on the left child.
   • Constraint Check: If the left child returns -1 (indicating it is unbalanced), immediately return -1 to propagate the error.
3. Recursive Step (Right): Recursively call the function on the right child.
   • Constraint Check: If the right child returns -1, immediately return -1.
4. Current Node Logic:
   • Calculate the absolute difference between the left and right heights.
   • If the difference is greater than 1, the current subtree is unbalanced. Return -1.
   • Otherwise, the current subtree is balanced. Return the height of the current node, which is max(left_height, right_height) + 1.
5. Final Result: In the main function, check if the helper function returns -1. If it does, the tree is not balanced. Otherwise, it is.

Execution Flow

Let's trace the algorithm on root = [1, 2, 3, 4, 5, null, null] (where 4 and 5 are children of 2).

1. Start at Root (1): Call dfs(1).
2. Traverse Left to Node (2): Call dfs(2).
3. Traverse Left to Node (4): Call dfs(4).
   • dfs(4.left) (null) returns 0.
   • dfs(4.right) (null) returns 0.
   • Node 4 checks abs(0-0) <= 1. Returns max(0,0) + 1 = 1.
4. Traverse Right to Node (5): Call dfs(5).
   • dfs(5.left) (null) returns 0.
   • dfs(5.right) (null) returns 0.
   • Node 5 checks abs(0-0) <= 1. Returns max(0,0) + 1 = 1.
5. Process Node (2):
   • Receives left = 1 (from Node 4), right = 1 (from Node 5).
   • Checks abs(1-1) <= 1. Returns max(1,1) + 1 = 2.
6. Traverse Right to Node (3): Call dfs(3).
   • Children are null. Returns 1.
7. Process Root (1):
   • Receives left = 2 (from Node 2), right = 1 (from Node 3).
   • Checks abs(2-1) <= 1. This is true.
   • Returns max(2,1) + 1 = 3.
8. Result: The initial call returned 3 (not -1), so the tree is balanced.

Proof of Correctness

The correctness relies on the inductive property of the postorder traversal.

• Base Case: An empty tree (null) is balanced by definition.
• Inductive Step: For any node $N$, if the left subtree is balanced and returns height $H_L$, and the right subtree is balanced and returns height $H_R$, then the tree rooted at $N$ is balanced if and only if $|H_L - H_R| \le 1$.
• The algorithm enforces this condition at every single node. If the condition fails at any node, -1 is returned. Since -1 propagates strictly upwards, the root will eventually receive -1 if any violation exists in the entire tree structure.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is highly reusable. Understanding how to bubble up values from leaves to root is critical for these related problems:

• LeetCode 104: Maximum Depth of Binary Tree - This is essentially the height calculation part of the Balanced Binary Tree solution without the balance check.
• LeetCode 124: Binary Tree Maximum Path Sum - Uses postorder traversal to calculate the max path contribution of a subtree and update a global maximum.
• LeetCode 145: Binary Tree Postorder Traversal - The foundational traversal mechanism used here.
• LeetCode 337: House Robber III - Returns a pair of values (robbed, not robbed) from children to parents using postorder DFS.

Reference Implementation

C++ Solution for LeetCode 110

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    bool isBalanced(TreeNode* root) {
15        return checkHeight(root) != -1;
16    }
17
18private:
19    // Returns height of subtree if balanced, or -1 if unbalanced
20    int checkHeight(TreeNode* node) {
21        if (node == nullptr) {
22            return 0;
23        }
24
25        int leftHeight = checkHeight(node->left);
26        if (leftHeight == -1) return -1; // Propagate failure
27
28        int rightHeight = checkHeight(node->right);
29        if (rightHeight == -1) return -1; // Propagate failure
30
31        if (abs(leftHeight - rightHeight) > 1) {
32            return -1; // Current node is unbalanced
33        }
34
35        return max(leftHeight, rightHeight) + 1;
36    }
37};

Java Solution for LeetCode 110

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public boolean isBalanced(TreeNode root) {
18        return dfsHeight(root) != -1;
19    }
20
21    // Returns the height of the tree if balanced, otherwise -1
22    private int dfsHeight(TreeNode node) {
23        if (node == null) {
24            return 0;
25        }
26
27        int leftHeight = dfsHeight(node.left);
28        if (leftHeight == -1) return -1; // Left subtree is unbalanced
29
30        int rightHeight = dfsHeight(node.right);
31        if (rightHeight == -1) return -1; // Right subtree is unbalanced
32
33        if (Math.abs(leftHeight - rightHeight) > 1) {
34            return -1; // Current node is unbalanced
35        }
36
37        return Math.max(leftHeight, rightHeight) + 1;
38    }
39}

Python Solution for LeetCode 110

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def isBalanced(self, root: Optional[TreeNode]) -> bool:
9        return self._check_height(root) != -1
10
11    def _check_height(self, node: Optional[TreeNode]) -> int:
12        if not node:
13            return 0
14        
15        left_height = self._check_height(node.left)
16        if left_height == -1:
17            return -1
18            
19        right_height = self._check_height(node.right)
20        if right_height == -1:
21            return -1
22        
23        if abs(left_height - right_height) > 1:
24            return -1
25            
26        return max(left_height, right_height) + 1