Balanced Binary Tree

LeetCode 110 | Difficulty: Easy

Easy

Problem Description

Given a binary tree, determine if it is height-balanced.

Example 1:

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

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

Constraints:

- The number of nodes in the tree is in the range `[0, 5000]`.

- `-10^4 <= Node.val <= 10^4`

Topics: Tree, Depth-First Search, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	N/A
Date	2018-04-23

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsBalanced(TreeNode root) {
       if(root==null) return true;
        int lh = Height(root.left);
    int rh = Height(root.right);
    return Math.Abs(lh-rh)<=1 && IsBalanced(root.left) && IsBalanced(root.right);

}
public int Height(TreeNode root)
{
    if (root == null)
        return 0;
    else return Math.Max(Height(root.left), Height(root.right)) + 1;
}

}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.