Solving Balanced Binary Tree in Go: Step-by-Step Guide

The Balanced Binary Tree problem is one of the most classic algorithmic challenges you will encounter on platforms like LeetCode (problem #110). It asks a deceptively simple question: given the root of a binary tree, determine whether it is height-balanced. A tree is considered height-balanced when, for every node, the depth of its left and right subtrees differs by no more than one. While the definition is straightforward, the implementation reveals important lessons about recursion, tree traversal, and algorithmic efficiency in Go.

What Is a Height-Balanced Binary Tree?

A binary tree is height-balanced if, at every node, the absolute difference between the heights of the left and right subtrees is at most one, and both subtrees themselves are also height-balanced. This property must hold recursively for the entire tree, not just the root node. A common misconception is to only check the root's children, but a tree can be unbalanced deep within a subtree while the root appears balanced.

Consider this example of a balanced tree:

At node 1, the left subtree has height 2 and the right subtree has height 1, so the difference is 1. At node 2, both children are leaves with height 1, so the difference is 0. Every node satisfies the condition, so the tree is balanced.

Now consider an unbalanced tree:

At node 1, the left subtree has height 2 while the right subtree has height 0. The difference is 2, which exceeds the allowed maximum of 1. Therefore, the tree is not balanced.

Why This Problem Matters

Balanced binary trees are foundational in computer science because they guarantee logarithmic time complexity for search, insertion, and deletion operations. Self-balancing structures like AVL trees and red-black trees were invented precisely to maintain this property automatically. Understanding how to verify balance manually teaches you several important skills:

How to reason about recursive tree traversal
How to compute subtree heights efficiently
How to avoid redundant work in recursive algorithms
How to propagate failure conditions upward through a call stack

In real-world Go applications, these patterns appear whenever you work with hierarchical data, parse nested structures, or validate the integrity of tree-like configurations.

Defining the Tree Structure in Go

Before solving the problem, you need a representation of a binary tree node. In Go, this is typically done with a struct containing integer data and pointers to left and right children.

package main

import (
    "fmt"
    "math"
)

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

This struct is the standard representation used in most Go coding challenges. The Val field holds the node's payload, while Left and Right are pointers that may be nil when a child is absent.

Approach 1: Top-Down Recursion (Naive)

The most intuitive approach is to compute the height of each subtree for every node and compare them. If the difference exceeds one, return false. Otherwise, recursively check both subtrees. This mirrors the definition of the problem almost word for word.

// height returns the height of the subtree rooted at node.
// A nil node has height 0.
func height(node *TreeNode) int {
    if node == nil {
        return 0
    }
    leftHeight := height(node.Left)
    rightHeight := height(node.Right)
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

// isBalancedNaive checks balance using top-down recursion.
func isBalancedNaive(root *TreeNode) bool {
    if root == nil {
        return true
    }
    leftHeight := height(root.Left)
    rightHeight := height(root.Right)

    diff := math.Abs(float64(leftHeight - rightHeight))
    if diff > 1 {
        return false
    }
    return isBalancedNaive(root.Left) && isBalancedNaive(root.Right)
}

This solution is correct but inefficient. For each node, you compute the height of its subtrees, and each height computation itself traverses the entire subtree. This leads to repeated work and a worst-case time complexity of O(n²) for a degenerate tree shaped like a linked list. The space complexity is O(n) due to the recursion stack.

Approach 2: Bottom-Up Recursion (Optimal)

The optimal solution computes the height and checks balance in a single pass. Instead of computing heights independently for each node, you compute the height of a subtree once and return it to the parent. If at any point a subtree is unbalanced, you propagate that information upward immediately, allowing the algorithm to short-circuit.

The trick is to use a sentinel value, such as -1, to indicate that a subtree is unbalanced. Whenever a recursive call returns -1, the caller immediately returns -1 as well, without performing further computation.

// checkHeight returns the height of the subtree rooted at node,
// or -1 if the subtree is unbalanced.
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
    }

    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

// abs returns the absolute value of an integer.
func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

// isBalanced returns true if the binary tree is height-balanced.
func isBalanced(root *TreeNode) bool {
    return checkHeight(root) != -1
}

This approach visits each node exactly once, giving it a time complexity of O(n). The space complexity remains O(n) in the worst case due to recursion depth, though for a balanced tree it is O(log n). By avoiding the math.Abs call and using a custom integer abs function, you also avoid unnecessary floating-point conversions.

Putting It All Together

Here is a complete, runnable program that constructs a sample tree, tests both approaches, and prints the results.

package main

import "fmt"

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

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
    }
    if leftHeight > rightHeight {
        return leftHeight + 1
    }
    return rightHeight + 1
}

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

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

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

    // Build an unbalanced tree:
    //     1
    //    /
    //   2
    //  /
    // 3
    unbalanced := &TreeNode{Val: 1}
    unbalanced.Left = &TreeNode{Val: 2}
    unbalanced.Left.Left = &TreeNode{Val: 3}

    fmt.Println("Balanced tree is balanced:", isBalanced(balanced))   // true
    fmt.Println("Unbalanced tree is balanced:", isBalanced(unbalanced)) // false
}

When you run this program, the output confirms that the first tree is balanced and the second is not. You can extend the test cases to include edge cases such as an empty tree, a single-node tree, and a tree where only one deep subtree causes imbalance.

Best Practices

Prefer the bottom-up approach. It runs in O(n) time and avoids the quadratic blowup of the naive method. Always look for opportunities to combine traversal and computation into a single pass.
Use sentinel values for early termination. Returning -1 to signal imbalance is a clean idiom that lets you short-circuit without introducing extra boolean parameters or global state.
Avoid floating-point operations for integer comparisons. Using a custom abs function keeps the code type-safe and avoids the overhead of converting between int and float64.
Handle nil nodes explicitly. A nil node has height 0 and is trivially balanced. Failing to check for nil before accessing child pointers will cause a panic in Go.
Test edge cases. Always verify behavior with an empty tree, a single node, a perfectly balanced tree, and a degenerate tree that resembles a linked list.
Watch recursion depth. For extremely deep trees, the recursion stack may become a concern. In production code, you might convert the algorithm to an iterative post-order traversal using an explicit stack.

Common Pitfalls

One frequent mistake is checking only the root node's children rather than every node in the tree. A tree can have balanced children at the root but an unbalanced subtree deeper down. Another pitfall is forgetting that the height of a nil node is 0, not -1. Mixing these conventions leads to off-by-one errors that are difficult to trace. Finally, relying on math.Abs with integers forces a conversion to float64, which is both unnecessary and slightly slower than a dedicated integer helper.

Conclusion

Solving the Balanced Binary Tree problem in Go is an excellent exercise in recursive thinking and algorithmic optimization. The naive top-down approach mirrors the problem definition but suffers from redundant computation, while the bottom-up approach achieves optimal O(n) performance by combining height calculation and balance checking into a single traversal. By using a sentinel value to propagate imbalance upward, you can write clean, efficient code that short-circuits as soon as a violation is detected. Mastering this pattern not only prepares you for coding interviews but also strengthens your ability to design efficient recursive solutions for any hierarchical data you encounter in real-world Go programs.