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.