Course4all
Join us on telegram
Home/dsa/Trees/Balanced Binary Tree

Balanced Binary Tree

Master this topic with zero to advance depth.

Balanced Binary Tree

Check if a tree is height-balanced.

Easy

Examples

Input: root = [3,9,20,null,null,15,7]
Output: true
Approach 1

Level I: Recursive DFS (Top-Down)

Intuition

For each node, compute the height of its left and right subtrees. If the difference is >1> 1, it's not balanced. Then recurse for both children.

⏱ O(N^2)💾 O(H)

Detailed Dry Run

root(3): H(L)=1, H(R)=2. Diff=1. OK. Recurse(9) and Recurse(20).

java
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        int lh = height(root.left), rh = height(root.right);
        return Math.abs(lh - rh) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }
}
Approach 2

Level II: Recursive with Memoization

Intuition

To optimize the O(N2)O(N^2) approach, we can cache the height of each node in a HashMap. This ensures that we only calculate the height of each node once, bringing the complexity down to O(N)O(N).

Logic

  1. Use a Map to store node -> height.
  2. In height(node), return map value if present.
  3. Recurse for balanced property using cached heights.
⏱ O(N)💾 O(N)

Detailed Dry Run

Map: {9:1, 15:1, 7:1, 20:2, 3:3}. Heights are fetched from Map in O(1) during balance check.

java
public class Main {
    Map<TreeNode, Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        if (map.containsKey(node)) return map.get(node);
        int h = 1 + Math.max(height(node.left), height(node.right));
        map.put(node, h);
        return h;
    }
}
Approach 3

Level III: Optimal (Bottom-Up DFS)

Intuition

Compute heights bottom-up. If any subtree is unbalanced, return -1 to signal failure to parents immediately.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node(20): L=1, R=1 -> height=2. root(3): L=1, R=2 -> height=3. Balanced.

java
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        int lh = height(node.left); if (lh == -1) return -1;
        int rh = height(node.right); if (rh == -1) return -1;
        if (Math.abs(lh - rh) > 1) return -1;
        return 1 + Math.max(lh, rh);
    }
}
← Previous QuestionDiameter of Binary Tree
Next Question →Construct Binary Tree from Preorder and Inorder Traversal