Check if Binary Tree is Balanced in DSA Go - Deep Dive

Overview - Check if Binary Tree is Balanced

What is it?

A binary tree is balanced if for every node, the height difference between its left and right subtrees is at most one. This means the tree is not too tall on one side compared to the other. Checking if a binary tree is balanced helps ensure efficient operations like searching and inserting. It is a common problem in computer science to keep trees optimized.

Why it matters

Without checking balance, a binary tree can become very tall and skinny, making operations slow like searching through a long list instead of a tree. Balanced trees keep operations fast and predictable, which is important for databases, file systems, and many software applications. Knowing if a tree is balanced helps maintain performance and avoid slowdowns.

Where it fits

Before this, you should understand what a binary tree is and how to measure tree height. After this, you can learn about self-balancing trees like AVL or Red-Black trees that automatically keep balance during updates.

Mental Model

Core Idea

A binary tree is balanced if no node has left and right subtrees differing in height by more than one.

Think of it like...

Imagine a seesaw with kids sitting on both sides. If one side is much heavier (taller subtree), the seesaw tips and is unbalanced. A balanced tree is like a seesaw level with kids evenly spread.

       Root
      /    \
  Left     Right
  Subtree  Subtree
  (height h) (height h or h-1)

Balanced if |height(left) - height(right)| <= 1

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Height

Concept: Learn how to find the height of a binary tree node.

The height of a node is the number of edges on the longest path from that node down to a leaf. For a leaf node, height is 0. For other nodes, height is 1 plus the maximum height of its children. Example: For a node with left child height 2 and right child height 3, node height = 1 + max(2,3) = 4.

Result

You can calculate the height of any node in a binary tree.

Understanding height is essential because balance depends on comparing subtree heights.

2

Foundation

What Makes a Tree Balanced?

Concept: Define the balance condition for every node in the tree.

A node is balanced if the difference between the heights of its left and right subtrees is at most 1. The whole tree is balanced if every node meets this condition. Example: If left subtree height is 3 and right subtree height is 1, difference is 2, so node is unbalanced.

Result

You can identify if a node or tree is balanced by checking height differences.

Balance is a local property checked at every node, not just the root.

3

Intermediate

Naive Approach: Separate Height and Balance Checks

🤔Before reading on: Do you think checking height separately for each node is efficient or slow? Commit to your answer.

Concept: Check balance by computing heights repeatedly for each node.

For each node, calculate left and right subtree heights, then check their difference. Recursively do this for all nodes. This approach is simple but inefficient because height is recalculated many times.

Result

Correct balance result but with high time cost, O(n^2) in worst case.

Knowing this naive method helps appreciate why optimization is needed.

4

Intermediate

Optimized Approach: Bottom-Up Height and Balance Check

🤔Before reading on: Will checking balance bottom-up with height return early on imbalance? Yes or no? Commit to your answer.

Concept: Combine height calculation and balance check in one recursion to avoid repeated work.

Use a function that returns height if subtree is balanced, or -1 if unbalanced. For each node: - Recursively get left height - Recursively get right height - If either is -1 or height difference > 1, return -1 - Else return 1 + max(left, right) If root returns -1, tree is unbalanced; otherwise balanced.

Result

Efficient O(n) time check with early stopping on imbalance.

Combining checks reduces repeated work and improves performance drastically.

5

Advanced

Implementing Balanced Check in Go

🤔Before reading on: Do you think the function should return a boolean or an integer height? Commit to your answer.

Concept: Write Go code using the optimized bottom-up approach to check balance.

Define a TreeNode struct with int value and left/right pointers. Write a helper function checkHeight(node *TreeNode) int: - If node is nil, return 0 - Get leftHeight = checkHeight(node.Left) - If leftHeight == -1, return -1 - Get rightHeight = checkHeight(node.Right) - If rightHeight == -1, return -1 - If abs(leftHeight - rightHeight) > 1, return -1 - Else return 1 + max(leftHeight, rightHeight) Main function isBalanced(root *TreeNode) bool calls checkHeight(root) != -1.

Result

The function returns true if tree is balanced, false otherwise.

Returning height or -1 encodes both height and balance status in one value.

6

Expert

Handling Edge Cases and Large Trees

🤔Before reading on: Can this approach handle very deep trees without stack overflow? Yes or no? Commit to your answer.

Concept: Consider recursion limits and edge cases like empty trees or skewed trees.

Empty tree (nil root) is balanced by definition. Very deep trees may cause stack overflow in recursion in some languages or environments. In Go, recursion depth is usually safe for typical trees, but iterative approaches or tail recursion optimization can be considered for extreme cases. Also, this method works correctly for skewed trees by detecting imbalance early.

Result

Robust balance check that handles all valid binary trees correctly.

Understanding recursion limits and edge cases prevents runtime errors in production.

Under the Hood

The algorithm uses recursion to explore the tree from bottom to top. At each node, it calculates the height of left and right subtrees. If any subtree is unbalanced, it propagates a special value (-1) upwards to signal imbalance. This avoids unnecessary checks once imbalance is found. The height is computed as 1 plus the maximum height of children, representing the longest path to a leaf.

Why designed this way?

This design avoids repeated height calculations that happen in naive top-down methods, reducing time complexity from O(n^2) to O(n). Early stopping on imbalance saves time by not exploring unnecessary nodes. The use of a special return value (-1) elegantly combines two pieces of information (height and balance) in one return type.

          checkHeight(node)
               │
      ┌────────┴────────┐
 leftHeight           rightHeight
    │                    │
  (int)                (int)
    │                    │
    └─────┬──────────────┘
          │
  if leftHeight == -1 or rightHeight == -1 or |leftHeight - rightHeight| > 1
          │
         return -1 (unbalanced)
          │
      else return 1 + max(leftHeight, rightHeight) (height)

Myth Busters - 4 Common Misconceptions

Quick: Does a balanced tree always have the same number of nodes on left and right? Commit yes or no.

Common Belief: A balanced tree means left and right subtrees have the same number of nodes.

Reality: Balance depends on height difference, not node count. Subtrees can have different numbers of nodes but still be balanced if heights differ by at most one.

Why it matters: Confusing node count with height can lead to wrong balance checks and inefficient tree operations.

Quick: Is it okay to check balance by only looking at the root node? Commit yes or no.

Common Belief: If the root node is balanced, the whole tree is balanced.

Reality: Every node must be balanced, not just the root. A subtree deep inside can be unbalanced even if the root looks balanced.

Why it matters: Ignoring internal nodes can miss imbalance, causing slow operations or bugs.

Quick: Does the naive method of checking height repeatedly run in linear time? Commit yes or no.

Common Belief: Calculating height separately for each node is efficient and fast.

Reality: Naive method can take O(n^2) time because height is recalculated many times for overlapping subtrees.

Why it matters: Using naive approach on large trees causes slow performance and timeouts.

Quick: Can the optimized method detect imbalance early and stop? Commit yes or no.

Common Belief: The optimized method always checks the entire tree even if imbalance is found early.

Reality: It returns -1 immediately when imbalance is detected, stopping further recursion.

Why it matters: Early stopping saves time and resources in large trees.

Expert Zone

1

The choice of -1 as a sentinel value cleverly encodes both failure and height in one integer, avoiding extra data structures.

2

In concurrent or parallel tree processing, balance checks can be done in parallel subtrees but require careful synchronization to combine results.

3

Some balanced tree definitions differ (like AVL vs Red-Black), so understanding this method's balance condition helps in adapting to other tree types.

When NOT to use

This method only checks if a tree is balanced; it does not rebalance it. For dynamic trees where insertions and deletions happen often, use self-balancing trees like AVL or Red-Black trees that maintain balance automatically.

Production Patterns

In production, this check is often used as a validation step after bulk tree construction or before expensive operations. It is also used in interview coding challenges to test understanding of recursion and tree properties.

Connections

AVL Trees

Builds-on

Understanding balance checking is foundational to AVL trees, which maintain this balance condition after every insertion or deletion.

Divide and Conquer Algorithms

Same pattern

The recursive height and balance check uses divide and conquer by solving subproblems (subtrees) and combining results.

Structural Engineering

Analogy in stability

Just like balanced trees ensure stability in data, balanced structures in engineering prevent collapse, showing how balance concepts cross domains.

Common Pitfalls

#1 Recomputing height for each node separately causes slow performance.

Wrong approach:

func height(node *TreeNode) int {
if node == nil {
return 0
}
return 1 + max(height(node.Left), height(node.Right))
}

func isBalanced(node *TreeNode) bool {
if node == nil {
return true
}
leftHeight := height(node.Left)
rightHeight := height(node.Right)
if abs(leftHeight - rightHeight) > 1 {
return false
}
return isBalanced(node.Left) && isBalanced(node.Right)
}

Correct approach:

func checkHeight(node *TreeNode) int {
if node == nil {
return 0
}
leftHeight := checkHeight(node.Left)
if leftHeight == -1 {
return -1
}
rightHeight := checkHeight(node.Right)
if rightHeight == -1 {
return -1
}
if abs(leftHeight - rightHeight) > 1 {
return -1
}
return 1 + max(leftHeight, rightHeight)
}

func isBalanced(root *TreeNode) bool {
return checkHeight(root) != -1
}

Root cause:

Not combining height and balance checks causes repeated height calculations.

#2 Checking balance only at root node and ignoring subtrees.

Wrong approach:

func isBalanced(root *TreeNode) bool {
leftHeight := height(root.Left)
rightHeight := height(root.Right)
return abs(leftHeight - rightHeight) <= 1
}

Correct approach:

Use recursive checkHeight function that verifies balance at every node, not just root.

Root cause:

Misunderstanding that balance is a global property requiring all nodes to be balanced.

#3 Returning boolean from helper function without height info makes combining results hard.

Wrong approach:

func checkBalanced(node *TreeNode) bool {
if node == nil {
return true
}
if !checkBalanced(node.Left) || !checkBalanced(node.Right) {
return false
}
leftHeight := height(node.Left)
rightHeight := height(node.Right)
return abs(leftHeight - rightHeight) <= 1
}

Correct approach:

Return height or -1 sentinel to combine height and balance info in one pass.

Root cause:

Separating height and balance checks leads to inefficiency and complex code.

Key Takeaways

A binary tree is balanced if every node's left and right subtree heights differ by at most one.

Naive balance checks recalculate heights repeatedly, causing slow O(n^2) time complexity.

Optimized bottom-up recursion returns height or -1 to combine balance check and height calculation efficiently in O(n) time.

Balance checking is essential for maintaining fast tree operations and is foundational for self-balancing trees.

Understanding recursion limits and edge cases ensures robust implementations in real-world applications.

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 the balance condition

   A balanced binary tree means for every node, the height difference between its left and right subtree is at most 1.

2. Step 2: Compare options with definition

   The height difference between left and right subtrees of every node is at most 1 matches the definition exactly. Other options describe different tree properties.

3. Final Answer:

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

4. Quick Check:

   Balanced tree = height difference ≤ 1 [OK]

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

Common Mistakes:

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

2. Which Go function signature correctly represents a function to check if a binary tree is balanced?

easy

A. func isBalanced(root *TreeNode) bool

B. func isBalanced(root TreeNode) int

C. func checkBalance(root *TreeNode) string

D. func balanced(root *TreeNode) void

Solution

1. Step 1: Identify correct parameter and return types

   The function should take a pointer to the root node and return a boolean indicating balanced or not.

2. Step 2: Match options with correct signature

   func isBalanced(root *TreeNode) bool matches: input is *TreeNode pointer, output is bool. Others have wrong return types or parameter types.

3. Final Answer:

   func isBalanced(root *TreeNode) bool -> Option A

4. Quick Check:

   Input pointer, output bool = correct signature [OK]

Hint: Check function returns bool and takes *TreeNode pointer [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Returning int or string instead of bool
• Using void (no return) for a check function

3. What will the output be for the following Go code snippet that checks if a binary tree is balanced?

package main
import "fmt"

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func height(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if leftHeight == -1 || rightHeight == -1 || abs(leftHeight-rightHeight) > 1 {
        return -1
    }
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

func isBalanced(root *TreeNode) bool {
    return height(root) != -1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Left.Left = &TreeNode{Val: 5}
    fmt.Println(isBalanced(root))
}

medium

A. Compilation error

B. true

C. false

D. Runtime panic

Solution

1. Step 1: Analyze tree structure and height function

   The tree is left-heavy: left subtree has height 3, right subtree height 1 at root. Difference is 2 > 1, so height returns -1.

2. Step 2: Check isBalanced return value

   isBalanced returns height(root) != -1, which is false here because height returned -1.

3. Final Answer:

   false -> Option C

4. Quick Check:

   Height difference > 1 means balanced = false [OK]

Hint: Height returns -1 if unbalanced; check != -1 for balanced [OK]

Common Mistakes:

• Assuming tree is balanced without checking height difference
• Confusing return values of height function
• Ignoring left-heavy subtree depth

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

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return false
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)
    if abs(leftHeight - rightHeight) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

medium

A. Uses incorrect logical operator in return

B. Returns false for empty tree instead of true

C. Missing base case for leaf nodes

D. Does not check height difference correctly

Solution

1. Step 1: Check base case for empty tree

   Function returns false if root is nil, but empty tree is balanced, so should return true.

2. Step 2: Verify other logic correctness

   Height difference check and recursive calls are correct. Only base case return is wrong.

3. Final Answer:

   Returns false for empty tree instead of true -> Option B

4. Quick Check:

   Empty tree is balanced, so base case must return true [OK]

Hint: Empty tree is balanced; base case must return true [OK]

Common Mistakes:

• Returning false for nil root
• Not checking both subtrees recursively
• Confusing logical AND with OR in recursion

5. Given a binary tree, how can you efficiently check if it is balanced without recalculating heights multiple times?

hard

A. Calculate height of left and right subtrees separately for each node

B. Check balance only at the root node

C. Use breadth-first traversal to count nodes at each level

D. Use a bottom-up recursion that returns height or -1 if unbalanced

Solution

1. Step 1: Understand naive approach inefficiency

   Calculating height separately for each node causes repeated work, leading to O(n²) time.

2. Step 2: Use bottom-up recursion for efficiency

   Return height if balanced, else -1 to stop early. This avoids repeated height calculations, achieving O(n) time.

3. Final Answer:

   Use a bottom-up recursion that returns height or -1 if unbalanced -> Option D

4. Quick Check:

   Bottom-up recursion avoids repeated height calls [OK]

Hint: Return -1 on unbalanced during height calc to stop early [OK]

Common Mistakes:

• Recalculating heights multiple times causing slow code
• Checking balance only at root misses subtree imbalance
• Using BFS which doesn't help with height difference