Introduction to Inverting a Binary Tree
The "Invert Binary Tree" problem is one of the most famous algorithmic challenges in computer science, partly because of the legendary story about a Google engineer who was asked to solve it on a whiteboard and famously failed. Despite its reputation, the problem is conceptually elegant and serves as an excellent introduction to tree traversal and recursive thinking. In this tutorial, we will explore what it means to invert a binary tree, why it matters, and how to implement a clean, idiomatic solution in Go.
What Is a Binary Tree?
A binary tree is a hierarchical data structure in which each node has at most two children, typically referred to as the left and right child. Binary trees are foundational structures used in search algorithms, expression parsing, and hierarchical data representation. In Go, we usually represent a binary tree node using a struct.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
What Does "Inverting" Mean?
Inverting a binary tree means swapping the left and right children of every node in the tree. After inversion, the left subtree becomes the right subtree and vice versa, recursively all the way down to the leaves. Visually, it is like mirroring the tree across its vertical axis.
For example, given the following tree:
4
/ \
2 7
/ \ / \
1 3 6 9
After inversion, the tree becomes:
4
/ \
7 2
/ \ / \
9 6 3 1
Why Inverting a Binary Tree Matters
While inverting a binary tree might seem like a purely academic exercise, it actually tests several fundamental skills that every developer should master:
- Recursion: The problem is a textbook example of how recursive thinking can simplify complex operations on recursive data structures.
- Tree traversal: You must visit every node in the tree, which reinforces understanding of pre-order, in-order, and post-order traversals.
- Pointer manipulation: In languages like Go, swapping pointers correctly is essential and teaches careful memory handling.
- Interview readiness: It remains a common interview question because it quickly reveals a candidate's comfort with recursion and data structures.
Beyond interviews, the same mirroring concept appears in graphics programming (image flipping), compiler design (AST transformations), and game development (procedural level generation).
Step-by-Step Solution in Go
Step 1: Define the Tree Node
First, we define the structure that represents each node in our binary tree. This struct holds an integer value and pointers to its left and right children.
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
Step 2: Implement the Recursive Inversion
The recursive approach is the most intuitive. The base case is simple: if the node is nil, there is nothing to invert. Otherwise, we swap the left and right children and recursively invert each subtree.
func invertTree(root *TreeNode) *TreeNode {
// Base case: empty tree
if root == nil {
return nil
}
// Swap the left and right children
root.Left, root.Right = root.Right, root.Left
// Recursively invert the subtrees
invertTree(root.Left)
invertTree(root.Right)
return root
}
Notice how Go's tuple assignment makes the swap concise: root.Left, root.Right = root.Right, root.Left. This single line performs the swap atomically without needing a temporary variable.
Step 3: Build a Helper to Print the Tree
To verify our solution, we need a way to visualize the tree. A simple level-order traversal using a queue works well for printing the tree breadth-first.
func printTree(root *TreeNode) {
if root == nil {
fmt.Println("empty tree")
return
}
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
fmt.Printf("%d ", node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
fmt.Println()
}
}
Step 4: Put It All Together
Now we can build a sample tree, print it, invert it, and print it again to confirm the result.
func main() {
// Construct the tree:
// 4
// / \
// 2 7
// / \ / \
// 1 3 6 9
root := &TreeNode{Val: 4}
root.Left = &TreeNode{Val: 2}
root.Right = &TreeNode{Val: 7}
root.Left.Left = &TreeNode{Val: 1}
root.Left.Right = &TreeNode{Val: 3}
root.Right.Left = &TreeNode{Val: 6}
root.Right.Right = &TreeNode{Val: 9}
fmt.Println("Original tree (level order):")
printTree(root)
invertTree(root)
fmt.Println("Inverted tree (level order):")
printTree(root)
}
When you run this program, the output should be:
Original tree (level order):
4
2 7
1 3 6 9
Inverted tree (level order):
4
7 2
9 6 3 1
Iterative Approach Using a Stack
Recursion is elegant, but it can cause stack overflow errors on very deep trees. An iterative approach using an explicit stack avoids this limitation. The logic is identical: visit each node and swap its children.
func invertTreeIterative(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// Swap children
node.Left, node.Right = node.Right, node.Left
// Push non-nil children onto the stack
if node.Left != nil {
stack = append(stack, node.Left)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
}
return root
}
You could also use a queue instead of a stack to perform a breadth-first inversion. The choice between stack and queue does not affect correctness, only the order in which nodes are processed.
Complexity Analysis
Understanding the time and space complexity of your solution is essential, especially in interview settings.
- Time complexity: O(n), where n is the number of nodes in the tree. Every node is visited exactly once.
- Space complexity (recursive): O(h), where h is the height of the tree. This accounts for the call stack. In the worst case (a skewed tree), h equals n, giving O(n). In a balanced tree, h is O(log n).
- Space complexity (iterative): O(n) in the worst case, since the stack or queue may hold up to n nodes.
Best Practices
Handle Edge Cases Explicitly
Always consider edge cases such as an empty tree (nil root) or a tree with a single node. Both recursive and iterative solutions above handle these gracefully because the base case returns nil immediately.
Prefer Idiomatic Go
Go's multiple assignment syntax makes pointer swaps clean and readable. Avoid introducing temporary variables unless absolutely necessary. Embrace Go's simplicity and avoid over-engineering the solution.
Write Tests
For any tree manipulation code, write table-driven tests. Go's testing package makes this straightforward. Here is a small example:
package main
import "testing"
func TestInvertTree(t *testing.T) {
tests := []struct {
name string
input *TreeNode
expected []int
}{
{
name: "nil tree",
input: nil,
expected: nil,
},
{
name: "single node",
input: &TreeNode{Val: 1},
expected: []int{1},
},
{
name: "balanced tree",
input: &TreeNode{
Val: 4,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 7},
},
expected: []int{4, 7, 2},
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
result := invertTree(tt.input)
// Add assertions comparing result with expected
_ = result
})
}
}
Choose the Right Approach
For most practical purposes, the recursive solution is preferred because it is concise and easy to reason about. If you are dealing with extremely deep trees or operating in environments with limited stack space, switch to the iterative version.
Common Pitfalls
- Forgetting the base case: Without the
nilcheck, the recursion will panic with a nil pointer dereference. - Swapping after recursion: If you swap children after the recursive calls, the result is still correct, but the logic becomes harder to follow. Swapping before recursion is the conventional approach.
- Mutating the original tree unintentionally: The
invertTreefunction modifies the tree in place. If you need to preserve the original, you must first deep-copy the tree before inverting.
Conclusion
Inverting a binary tree is a deceptively simple problem that reinforces essential programming concepts: recursion, tree traversal, pointer manipulation, and complexity analysis. In Go, the solution becomes particularly elegant thanks to tuple assignment and the language's straightforward struct semantics. Whether you choose the recursive or iterative approach, the key is to understand the underlying mechanics of how trees are structured and traversed. By mastering this problem, you build a strong foundation for tackling more complex tree and graph algorithms, and you gain confidence in writing clean, idiomatic Go code that handles data structures with care.