Check if Binary Tree is Balanced in DSA Go

Mental Model

A balanced binary tree means no part is much taller than its sibling parts. We check if every node's left and right sides differ in height by at most one.

Analogy: Imagine a tree with branches on both sides. If one side is much longer than the other, the tree might fall. We want to make sure both sides grow evenly, like a well-trimmed bush.

      1
     / \
    2   3
   / 
  4  

Balanced: left and right heights differ by at most 1

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2, right child 3; 2 has left child 4

Goal: Determine if the tree is balanced by checking height differences at each node

Step 1: Check height of node 4 (leaf)

Node 4 height = 1 (no children)

Why: Leaf nodes have height 1 (max of empty subtrees height 0 + 1), base case for height calculation

Step 2: Check height of node 2: left child height 1, right child height 0 (no right child)

Height difference at node 2 = 1 (|1 - 0|)

Why: Difference is 1, which is allowed for balanced

Step 3: Check height of node 3 (leaf)

Node 3 height = 1

Why: Leaf node height is 1

Step 4: Check height of node 1: left child height 2, right child height 1

Height difference at node 1 = 1 (|2 - 1|)

Why: Difference is 1, tree remains balanced

Result:

Tree is balanced because all nodes have height difference ≤ 1

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode defines a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// checkHeight returns the height of the node if balanced, else -1
func checkHeight(node *TreeNode) int {
    if node == nil {
        return 0 // base case: empty tree height 0
    }

    leftHeight := checkHeight(node.Left) // height of left subtree
    if leftHeight == -1 {
        return -1 // left subtree not balanced
    }

    rightHeight := checkHeight(node.Right) // height of right subtree
    if rightHeight == -1 {
        return -1 // right subtree not balanced
    }

    if abs(leftHeight-rightHeight) > 1 {
        return -1 // current node not balanced
    }

    return max(leftHeight, rightHeight) + 1 // height of current node
}

// IsBalanced returns true if tree is balanced
func IsBalanced(root *TreeNode) bool {
    return checkHeight(root) != -1
}

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    // Build tree: 1
    //           /   \
    //          2     3
    //         / 
    //        4
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}

    fmt.Println(IsBalanced(root))
}

if node == nil { return 0 }

base case: empty subtree height is 0

leftHeight := checkHeight(node.Left)

recursively get left subtree height

if leftHeight == -1 { return -1 }

if left subtree unbalanced, propagate failure

rightHeight := checkHeight(node.Right)

recursively get right subtree height

if rightHeight == -1 { return -1 }

if right subtree unbalanced, propagate failure

if abs(leftHeight-rightHeight) > 1 { return -1 }

check current node balance by height difference

return max(leftHeight, rightHeight) + 1

return height of current node

return checkHeight(root) != -1

final balanced check: no -1 means balanced

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to compute heights and check balance

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach recomputes heights repeatedly causing O(n^2) time; this method computes height bottom-up once per node

Edge Cases

Empty tree (root is nil)

Returns true since empty tree is balanced

DSA Go

if node == nil { return 0 }

Single node tree

Returns true since single node has no imbalance

DSA Go

if node == nil { return 0 }

Unbalanced tree with one side deeper by more than 1

Returns false as height difference > 1 detected

DSA Go

if abs(leftHeight-rightHeight) > 1 { return -1 }

When to Use This Pattern

When a problem asks if a binary tree is balanced, use a bottom-up height check with early stop to efficiently detect imbalance.

Common Mistakes

Mistake: Recomputing subtree heights multiple times causing slow O(n^2) solution
Fix: Use a helper function that returns height or -1 to avoid repeated height calculations

Summary

Checks if every node's left and right subtree heights differ by at most one.

Use when you need to verify if a binary tree is balanced for performance or correctness.

The key is to compute heights bottom-up and stop early if imbalance is found.

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