Balanced Binary Tree

📋

Problem

Imagine you are designing a system that needs to keep data balanced for efficient retrieval, like a balanced family tree where no branch is too deep compared to others.

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Input: The root node of a binary tree. Output: Return true if the tree is height-balanced, otherwise false.

1 ≤ n ≤ 10^5 (number of nodes)Node values can be any integerTree can be skewed or complete

Edge cases: Empty tree → true (an empty tree is balanced)Single node tree → true (only one node, balanced)Completely skewed tree (all nodes only on one side) → false

</>

IDE

def isBalanced(root: Optional[TreeNode]) -> bool:public boolean isBalanced(TreeNode root)bool isBalanced(TreeNode* root)function isBalanced(root)

def isBalanced(root):
    # Write your solution here
    pass

class Solution {
    public boolean isBalanced(TreeNode root) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isBalanced(TreeNode* root) {
    // Write your solution here
    return false;
}

function isBalanced(root) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueFailing to detect imbalance in skewed or deep subtree cases due to missing or incorrect height difference checks.✅ Add condition to return false immediately if abs(left_height - right_height) > 1 at any node.

Wrong: falseIncorrectly returning false for empty or single-node trees by not handling base cases.✅ Return true immediately if root is null or if node has no children.

Wrong: trueNot using early exit, causing incorrect results when imbalance is detected deep in the tree.✅ Implement early exit by returning a sentinel value (e.g., -1) to indicate imbalance and propagate it up.

Wrong: TLEUsing brute force approach that recomputes height for each node causing O(n^2) complexity.✅ Use a single postorder traversal that returns height and balance status simultaneously to achieve O(n).

✓

Test Cases

Try testing your solution on empty and single-node trees to catch base case bugs.

Consider trees with deep imbalances and verify your early exit logic.

Optimize your solution to avoid repeated height computations to pass large input tests.

t1_01basic

Input{"root":[3,9,20,null,null,15,7]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The left subtree height is 1, right subtree height is 2, difference is 1 which is allowed.

💡 Check the height difference between left and right subtrees at every node.

💡 Use postorder traversal to compute heights and check balance bottom-up.

💡 Return false immediately if any subtree height difference exceeds 1.

Why it failed: Returned false or incorrect result because height difference check is missing or incorrect at some node. Fix by ensuring abs(left_height - right_height) <= 1 at every node.

✓ Correctly identifies balanced tree using height difference checks.

t1_02basic

Input{"root":[1,2,2,3,3,null,null,4,4]}

Expectedfalse

⏱ Performance - must finish in 2000ms

The left subtree is deeper by more than 1 level at node 2, so the tree is unbalanced.

💡 Check subtree heights recursively for each node.

💡 If any node's left and right subtree heights differ by more than 1, return false.

💡 Use early exit to avoid unnecessary checks once imbalance is found.

Why it failed: Returned true despite subtree height difference > 1. Fix by adding early exit when imbalance detected.

✓ Correctly detects unbalanced tree with subtree height difference > 1.

t2_01edge

Input{"root":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

An empty tree is balanced by definition.

💡 Consider the base case when root is null.

💡 An empty tree has height 0 and is balanced.

💡 Return true immediately if root is null.

Why it failed: Returned false or error on empty tree input. Fix by handling null root as balanced.

✓ Correctly returns true for empty tree.

t2_02edge

Input{"root":[1]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node tree is balanced as both subtrees are empty.

💡 Check that single node with no children is balanced.

💡 Height difference is zero at root.

💡 Return true if no children or subtrees are balanced.

Why it failed: Returned false for single node tree. Fix by correctly handling leaf nodes as balanced.

✓ Correctly returns true for single node tree.

t2_03edge

Input{"root":[1,2,null,3,null,4,null,5]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Completely skewed tree with nodes only on left side is unbalanced.

💡 Check height difference at each node in skewed tree.

💡 Height difference accumulates to more than 1 at root.

💡 Return false when imbalance detected in skewed structure.

Why it failed: Returned true for skewed tree. Fix by ensuring height difference check is done at every node.

✓ Correctly identifies skewed tree as unbalanced.

t3_01corner

Input{"root":[1,2,2,3,null,null,3,4,null,null,4]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tree where imbalance occurs deep in subtree; tests early exit correctness.

💡 Check if your solution stops checking after detecting imbalance.

💡 Use postorder traversal with early return on imbalance.

💡 Return false immediately when a subtree is unbalanced to avoid extra work.

Why it failed: Returned true despite deep subtree imbalance. Fix by implementing early exit in recursion when imbalance found.

✓ Correctly detects deep subtree imbalance and exits early.

t3_02corner

Input{"root":[1,2,2,3,null,null,3,4,null,null,4,5]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded recursion: extra nodes cause imbalance.

💡 Ensure you do not double count nodes or heights.

💡 Check that each node is processed exactly once in postorder.

💡 Avoid counting nodes multiple times or skipping subtrees.

Why it failed: Returned true due to incorrect height calculation or double counting. Fix by correctly computing height once per node.

✓ Correctly computes height and detects imbalance.

t3_03corner

Input{"root":[1,2,2,3,3,null,null,4,4,null,null,null,null,5]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy trap: assuming local balance implies global balance is incorrect.

💡 Check balance at every node, not just root or leaves.

💡 Use bottom-up postorder traversal to propagate balance info.

💡 Do not assume subtrees are balanced without verification.

Why it failed: Returned true by only checking root or leaves. Fix by verifying balance at all nodes recursively.

✓ Correctly verifies balance at all nodes.

t4_01performance

Input{"root":[1,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10]}

Expectednull

⏱ Performance - must finish in 2000ms

n=10 (skewed tree) tests O(n) complexity; brute force O(n^2) will time out for large n.

💡 Use postorder traversal with early exit to achieve O(n) time.

💡 Avoid recomputing heights multiple times.

💡 Return -1 or false immediately when imbalance detected.

Why it failed: TLE due to O(n^2) brute force height recomputation. Fix by using single postorder traversal with early exit.

✓ Solution runs in O(n) time using optimized recursion.

Practice

1. Consider the following iterative postorder traversal code to compute the diameter of a binary tree. Given the tree: 1 / \ 2 3 / 4 What is the final value of the variable diameter after the function completes?

easy

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: Trace heights and diameter updates for each node.

   Node 4: height=1, diameter=0; Node 2: left=1 (node4), right=0, diameter=max(0,1)=1; Node 3: height=1, diameter=1; Node 1: left=2 (node2), right=1 (node3), diameter=max(1,2+1=3)=3.

2. Step 2: Verify final diameter value returned.

   The diameter is the maximum sum of left and right heights at any node, which is 3 edges, so the longest path length is 3 edges.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest path is from node 4 to node 3 with length 3 edges [OK]

Hint: Diameter counts edges, not nodes [OK]

Common Mistakes:

• Confusing diameter as number of nodes
• Off-by-one in height calculation
• Missing right subtree height

2. You are given a binary tree where each node contains a non-negative integer value. You want to maximize the sum of values you can collect by selecting nodes such that no two directly connected nodes (parent-child) are both selected. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that always picks the node with the highest value first.

B. Use a depth-first search with dynamic programming that returns two values per node: max if robbing it and max if not robbing it.

C. Use a breadth-first search to select nodes level by level, picking the maximum values at alternate levels.

D. Use a brute force recursion that tries all subsets of nodes without any memoization.

Solution

1. Step 1: Understand the problem constraints

   The problem requires selecting nodes in a tree such that no parent and child are both selected, maximizing the sum of selected nodes.

2. Step 2: Identify the suitable algorithmic pattern

   A greedy or BFS level-based approach fails because the tree structure and adjacency constraints are complex. Brute force is correct but inefficient. The optimal solution uses DFS with DP returning two values per node: max if robbing it and max if not robbing it, ensuring all subproblems are solved optimally.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DFS with two-value DP handles adjacency constraints correctly [OK]

Hint: Tree + no adjacent nodes -> DFS with two-value DP [OK]

Common Mistakes:

• Assuming greedy or level-based selection works
• Trying brute force without memoization

3. You are given a binary tree and need to determine if it is a mirror of itself (i.e., symmetric around its center). Which approach guarantees an optimal solution that efficiently checks this property by comparing nodes in a mirrored fashion?

easy

A. Use a recursive DFS that simultaneously compares the left subtree of one node with the right subtree of the other node, returning false immediately on mismatch.

B. Perform a level-order traversal and compare nodes at each level from left to right.

C. Traverse the tree in preorder and check if the sequence of node values is a palindrome.

D. Use a brute force approach that generates all subtree permutations and checks for symmetry.

Solution

1. Step 1: Understand the problem requires mirrored subtree comparison

   The problem asks if the tree is symmetric, meaning the left subtree is a mirror reflection of the right subtree.

2. Step 2: Identify the approach that compares mirrored nodes recursively with early exit

   The recursive DFS approach compares left subtree nodes with right subtree nodes in mirrored positions and returns false immediately if any mismatch is found, ensuring efficiency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Mirrored recursive DFS matches problem requirements [OK]

Hint: Symmetry requires mirrored subtree comparison [OK]

Common Mistakes:

• Assuming preorder traversal palindrome check works
• Using level-order traversal without mirrored comparison
• Trying brute force subtree permutations

4. The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.

def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx < mid:  # Bug here
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not null

medium

A. Line with 'if idx < mid:'

B. Line with 'return root is not null'

C. Line with 'root = root.right'

D. Line with 'left, right = 0, 2**(h - 1) - 1'

Solution

1. Step 1: Understand binary search condition

   The condition should be 'if idx <= mid' to correctly include mid index in left subtree.

2. Step 2: Identify impact of bug

   Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct binary search must include mid index [OK]

Hint: Binary search must use <= to include mid index [OK]

Common Mistakes:

• Using < instead of <= in binary search condition

5. What is the time complexity of the parent pointer + ancestor set approach for finding the Lowest Common Ancestor in a binary tree with n nodes and height h?

medium

A. O(h^2) because ancestor set lookups take O(h) each and we do up to h lookups

B. O(n^2) because each node's parent is checked multiple times

C. O(n) to build parent map plus O(h) to find LCA, total O(n)

D. O(n log n) due to sorting ancestors before comparison

Solution

1. Step 1: Identify parent map construction cost

   Building the parent map requires visiting each node once, O(n).

2. Step 2: Analyze ancestor set and LCA search

   Ancestor set insertion and lookup are O(1) average. Traversing up to height h for p and q is O(h). Total is O(n) + O(h) ≈ O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Parent map O(n) + ancestor lookup O(h) = O(n) total [OK]

Hint: Parent map build dominates; ancestor lookup is O(h) [OK]

Common Mistakes:

• Confusing ancestor set lookup as O(h)
• Assuming sorting ancestors needed
• Overestimating repeated parent checks