Check if Binary Tree is Balanced in DSA Java - Execution Trace

Concept Flow - Check if Binary Tree is Balanced

Start at root node

↓

Check left subtree height

↓

Check right subtree height

↓

Compare heights difference <= 1?

Yes No↓

Check left balanced?

↓

Check right balanced?

↓

Return true if both balanced

Start from root, recursively check left and right subtree heights and balance, return false if difference > 1, else true if all subtrees balanced.

Execution Sample

DSA Java

class Node {
  int val;
  Node left, right;
}

boolean isBalanced(Node root) {
  return checkHeight(root) != -1;
}

int checkHeight(Node node) {
  if (node == null) return 0;
  int left = checkHeight(node.left);
  if (left == -1) return -1;
  int right = checkHeight(node.right);
  if (right == -1) return -1;
  if (Math.abs(left - right) > 1) return -1;
  return Math.max(left, right) + 1;
}

This code checks if a binary tree is balanced by recursively computing subtree heights and returning -1 if imbalance is found.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Balance Check	Return Value	Tree State
1	Check height	Root (1)	?	?	Pending	?	Root node exists
2	Check height	Left child (2)	?	?	Pending	?	At node 2
3	Check height	Left child of 2 (4)	0	0	Balanced	1	Leaf node 4
4	Check height	Right child of 2 (5)	0	0	Balanced	1	Leaf node 5
5	Balance check at node 2	2	1	1	Balanced	2	Subtree rooted at 2 balanced
6	Check height	Right child (3)	?	?	Pending	?	At node 3
7	Check height	Left child of 3 (null)	0	0	Balanced	0	Null node treated as height 0
8	Check height	Right child of 3 (6)	0	0	Balanced	1	Leaf node 6
9	Balance check at node 3	3	0	1	Balanced	2	Subtree rooted at 3 balanced
10	Balance check at root	1	2	2	Balanced	3	Whole tree balanced
11	Final result	Root (1)	-	-	-	true	Tree is balanced

💡 All nodes checked, no height difference > 1 found, tree is balanced.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 7	After Step 8	After Step 9	After Step 10	Final
node	Root (1)	Node 4	Node 5	Node 2	null	Node 6	Node 3	Root (1)	Root (1)
leftHeight	?	0	0	1	0	0	0	2	2
rightHeight	?	?	0	1	?	0	1	2	2
returnValue	?	1	1	2	0	1	2	3	true

Key Moments - 3 Insights

Why do we return -1 when a subtree is unbalanced?

Returning -1 signals imbalance immediately, so parent calls can stop further checks early, as seen in steps 3-5 and 7-9 where -1 would propagate up.

Why is a null node height 0?

Null nodes represent empty subtrees, so their height is 0, which is the base case in step 7, allowing leaf nodes to compute height correctly.

How do we know the tree is balanced at the root?

At step 10, left and right subtree heights are equal (2 and 2), difference ≤ 1, so the root is balanced, leading to final true at step 11.

Visual Quiz - 3 Questions

Look at the execution table, what is the return value after checking node 2?

A 2

B 1

C -1

D 0

💡 Hint

Check row with Step 5 where node 2 is balanced and returns height 2.

At which step does the algorithm confirm the right subtree of the root is balanced?

A Step 6

B Step 9

C Step 7

D Step 10

💡 Hint

Look for the balance check at node 3 in the execution table.

If the left child of node 3 had height 2 instead of 0, what would happen at step 9?

A Algorithm would continue checking right subtree

B Return value would be 3 indicating balanced

C Return value would be -1 indicating imbalance

D No change, still balanced

💡 Hint

Recall balance check fails if height difference > 1, causing return -1.

Concept Snapshot

Check if Binary Tree is Balanced:
- Recursively find left and right subtree heights
- If difference > 1, return -1 (unbalanced)
- If any subtree returns -1, propagate -1 up
- If root returns height ≥ 0, tree is balanced
- Use helper function returning height or -1
- Final check: isBalanced = (helper(root) != -1)

Full Transcript

This visualization shows how to check if a binary tree is balanced by recursively computing subtree heights. Starting at the root, the algorithm checks the left and right subtree heights. If the difference between these heights is more than 1, it returns -1 to indicate imbalance. This -1 value propagates up to stop further checks early. Null nodes have height 0. The execution table traces each node visited, the heights computed, and balance checks performed. The variable tracker shows how node pointers and heights change step-by-step. Key moments clarify why -1 is used, why null nodes have height 0, and how the final balanced result is determined. The quiz tests understanding of return values and balance checks at specific steps. The snapshot summarizes the approach in concise steps.

Practice

1. What does it mean for a binary tree to be balanced?

easy

A. The height difference between left and right subtrees of every node is at most 1

B. All nodes have two children

C. The tree has the same number of nodes on left and right

D. The tree is a complete binary tree

Solution

1. Step 1: Understand balance condition

   A balanced binary tree means the height difference between left and right subtrees of every node is at most 1.

2. Step 2: Compare other options

   Options A, B, and C describe different tree properties but not the balance condition.

3. Final Answer:

   The height difference between left and right subtrees of every node is at most 1 -> Option A

4. Quick Check:

   Balance means height difference ≤ 1 [OK]

Hint: Balance means height difference ≤ 1 at every node [OK]

Common Mistakes:

• Confusing balanced with complete tree
• Thinking balance means equal number of nodes
• Assuming all nodes must have two children

2. Which Java method signature correctly defines a function to check if a binary tree is balanced?

easy

A. boolean isBalanced(TreeNode root) void

B. public boolean isBalanced(TreeNode root)

C. public void isBalanced(TreeNode root) returns boolean

D. boolean isBalanced(TreeNode root) public

Solution

1. Step 1: Check Java method syntax

   Correct Java method signature includes access modifier, return type, method name, and parameters: public boolean isBalanced(TreeNode root)

2. Step 2: Identify incorrect syntax

   Options A, C, and D have invalid order or keywords not used in Java method declarations.

3. Final Answer:

   public boolean isBalanced(TreeNode root) -> Option B

4. Quick Check:

   Java method syntax: access returnType name(params) [OK]

Hint: Java method: access modifier + return type + name + parameters [OK]

Common Mistakes:

• Mixing return type and void
• Wrong keyword order
• Missing access modifier

3. What will be the output of the following code snippet?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}

public class Solution {
  public boolean isBalanced(TreeNode root) {
    if (root == null) return true;
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) return false;
    return 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));
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.left.left.left = new TreeNode(5);
    Solution sol = new Solution();
    System.out.println(sol.isBalanced(root));
  }
}

medium

A. false

B. true

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Calculate subtree heights

   Left subtree of root has height 3 (nodes 2 -> 4 -> 5), right subtree has height 1 (node 3). Difference is 2 > 1.

2. Step 2: Check balance condition

   Since height difference > 1 at root, isBalanced returns false.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Height difference > 1 means unbalanced = false [OK]

Hint: Check height difference at root first for quick balance check [OK]

Common Mistakes:

• Ignoring height difference > 1
• Assuming tree is balanced by default
• Confusing height with node count

4. Identify the bug in this code snippet that checks if a binary tree is balanced:

public boolean isBalanced(TreeNode root) {
  if (root == null) return true;
  int leftHeight = height(root.left);
  int rightHeight = height(root.right);
  if (Math.abs(leftHeight - rightHeight) > 1) return false;
  return 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));
}

medium

A. Incorrect height calculation formula

B. Missing base case for null root

C. Using || instead of && in recursive call

D. No return statement in height method

Solution

1. Step 1: Analyze recursive calls

   The code uses || (OR) to combine left and right subtree balance checks, which returns true if either subtree is balanced.

2. Step 2: Correct logic for balance

   Both left and right subtrees must be balanced, so && (AND) should be used instead of ||.

3. Final Answer:

   Using || instead of && in recursive call -> Option C

4. Quick Check:

   Balance requires both subtrees balanced: use && [OK]

Hint: Use && to ensure both subtrees are balanced [OK]

Common Mistakes:

• Using || instead of &&
• Forgetting base case
• Miscomputing height

5. Given a binary tree, how can you optimize the balance check to avoid repeated height calculations?

hard

A. Use a queue to traverse nodes level by level

B. Calculate height separately for left and right subtrees multiple times

C. Only check balance at the root node

D. Calculate height and balance in one recursive function returning a special value

Solution

1. Step 1: Identify inefficiency in naive approach

   Naive method calculates height repeatedly for subtrees, causing extra work.

2. Step 2: Use combined recursive function

   Return height if subtree is balanced, else return -1 to indicate imbalance, avoiding repeated height calls.

3. Final Answer:

   Calculate height and balance in one recursive function returning a special value -> Option D

4. Quick Check:

   Combine height and balance check to optimize [OK]

Hint: Return -1 on imbalance to stop early and save time [OK]

Common Mistakes:

• Recalculating height multiple times
• Using level order traversal which doesn't help balance check
• Checking balance only at root