Check if Binary Tree is Balanced in DSA Go - 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

We check the height of left and right subtrees at each node and ensure their difference is at most 1, recursively verifying balance.

Execution Sample

DSA Go

func isBalanced(root *Node) bool {
  _, balanced := checkHeight(root)
  return balanced
}

func checkHeight(node *Node) (int, bool) {
  if node == nil { return 0, true }
  leftHeight, leftBalanced := checkHeight(node.Left)
  rightHeight, rightBalanced := checkHeight(node.Right)
  if !leftBalanced || !rightBalanced || leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1 {
    return 0, false
  }
  h := leftHeight
  if rightHeight > h {
    h = rightHeight
  }
  return h + 1, true
}

This code recursively checks subtree heights and balance, returning false if any subtree is unbalanced.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Balanced?	Visual State
1	Visit root	1	?	?	?	1 / \ 2 3
2	Visit left child	2	?	?	?	1 / \ 2 3 / 4
3	Visit left-left child	4	0	0	true	1 / \ 2 3 / 4
4	Return from node 4	4	0	0	true	1 / \ 2 3 / 4
5	Return from node 2	2	1	0	true	1 / \ 2 3 / 4
6	Visit right child	3	?	?	?	1 / \ 2 3 / 4
7	Visit right-right child	5	0	0	true	1 / \ 2 3 / 4 \ 5
8	Return from node 5	5	0	0	true	1 / \ 2 3 / 4 \ 5
9	Return from node 3	3	0	1	true	1 / \ 2 3 / 4 \ 5
10	Return from root	1	2	2	true	1 / \ 2 3 / 4 \ 5
11	Check balance condition	1	2	2	true	Balanced tree confirmed
12	End	-	-	-	-	Traversal complete, tree is balanced

💡 Traversal ends when all nodes are visited and balance conditions hold at every node.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 8	After Step 10	Final
node	root (1)	4	2	5	1	nil
leftHeight	?	0	1	0	2	2
rightHeight	?	?	0	1	2	2
balanced	?	true	true	true	true	true

Key Moments - 3 Insights

Why do we return height 0 and balanced true for a nil node?

Because a nil node means no subtree, so height is 0 and it's balanced by definition (see Step 3 and Step 8).

Why do we check balance after getting left and right heights?

Because balance depends on height difference and subtree balance, as shown in Steps 9 and 10 where we compare heights and balanced flags.

What happens if the height difference is more than 1?

The function returns false immediately (not shown in this balanced example), stopping further checks and marking the tree unbalanced.

Visual Quiz - 3 Questions

Look at the execution table, what is the leftHeight at Step 10?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Left Height' column at Step 10 in the execution_table.

At which step does the function confirm the tree is balanced?

A Step 11

B Step 9

C Step 5

D Step 12

💡 Hint

Look for the step where 'Balanced tree confirmed' appears in the Visual State column.

If node 3 had a right child making rightHeight 4, what would happen at Step 10?

A leftHeight would increase

B balanced would be false

C balanced would be true

D function would continue without change

💡 Hint

Recall the balance condition checks if height difference > 1, see Step 10 logic.

Concept Snapshot

Check if Binary Tree is Balanced:
- Recursively get left and right subtree heights
- If difference > 1, tree is unbalanced
- Return height and balanced status up the call stack
- Base case: nil node height=0, balanced=true
- Final result: true if all nodes balanced

Full Transcript

To check if a binary tree is balanced, we start at the root and recursively check the height of left and right subtrees. For each node, we calculate the height of its left and right children. If the difference between these heights is more than 1, the tree is not balanced. We also check if the left and right subtrees themselves are balanced. If all nodes satisfy the balance condition, the tree is balanced. The base case is when a node is nil, which means height 0 and balanced true. This process continues until all nodes are checked, returning the final balanced status.