Invert a Binary Tree in Go

In the world of computer science and software development, binary trees are fundamental data structures that play a crucial role in various algorithms and applications. These hierarchical structures are used for tasks ranging from efficient searching to data sorting and more. While binary trees come in various forms, the concept of inverting a binary tree has always held a special place as a classic problem in computer science.

In this article, we will explore how to invert them using the Go programming language. The process of inverting a binary tree involves flipping its structure in a way that the left and right subtrees swap positions for each node, creating a mirror image of the original tree. This seemingly simple operation has far-reaching implications, affecting not only tree traversal but also numerous real-world applications such as optimizing search algorithms and data representation.

We'll leverage the power of Go to tackle this binary tree inversion problem head-on.

The Problem

Inverting a binary tree is like flipping it into a mirror image of itself. Imagine a tree where each node has a left and right branch.

When you invert the tree, you swap the left and right branches for every node. So, if a node had a left branch with some data on the left and a right branch with data on the right, after inverting, the left branch becomes the right branch, and the right branch becomes the left branch.

It's like looking at the tree in a mirror – what was on the left is now on the right, and vice versa.

Visualizing

Let's visually walk through the process of inverting the tree.

In each step, we invert the subtree.

The Solution

Let us first create our tree data structure to represent the above binary tree.

package main

type Node struct {
    data int
}

func NewNode(data int) Node {
    return Node{
        data: data,
    }
}

type BinaryTree struct {
    value Node
    left  *BinaryTree
    right *BinaryTree
}

func NewBinaryTree(v Node, l *BinaryTree, r *BinaryTree) *BinaryTree {
    return &BinaryTree{
        value: v,
        left:  l,
        right: r,
    }
}

func InvertBinaryTree(tree *BinaryTree) {
    // TODO: Solution
}

func main() {
    tree := NewBinaryTree(
        NewNode(1),
        NewBinaryTree(
            NewNode(4),
            NewBinaryTree(
                NewNode(2),
                NewBinaryTree(
                    NewNode(3),
                    nil,
                    nil,
                ),
                NewBinaryTree(
                    NewNode(6),
                    nil,
                    nil,
                ),
            ),
            NewBinaryTree(
                NewNode(5),
                nil,
                nil,
            ),
        ),
        NewBinaryTree(
            NewNode(6),
            NewBinaryTree(
                NewNode(7),
                nil,
                nil,
            ),
            NewBinaryTree(
                NewNode(8),
                nil,
                nil,
            ),
        ),
    )
}

Below is the algorithm to invert the tree

func InvertBinaryTree(tree *BinaryTree) {
    queue := []*BinaryTree{tree}
    for {
        if len(queue) == 0 {
            break
        }
        // pop item from queue
        current := queue[len(queue)-1]
        queue = queue[:len(queue)-1]

        if current == nil {
            continue
        }
        // Swap left and right sub trees
        current.right, current.left = current.left, current.right
        queue = append(queue, current.left, current.right)
    }
}

1. Starting with a Queue: The function starts by creating an empty queue. A queue is like a line of people, where the first person in line is the first to be served.

2. Adding the Tree: The binary tree that you want to invert is passed as an argument to the function, and it's added to the queue. The queue now contains the root of the tree.

3. Processing the Tree:

   • The code enters a loop that continues until the queue is empty.

   • Inside the loop, it takes the last item (the person at the end of the line) from the queue and calls it current. In a binary tree, current represents the current node we're working on.

   • If current is nil (which means there's nothing there), the code skips it and continues to the next item in the queue.

4. Swapping Left and Right: If current is not nil, it means there's something in that node of the tree. Here, the magic happens: it swaps the left and right sub-trees of the current node. In other words, what was on the left side of this node is now on the right side, and what was on the right is now on the left.

5. Queue Update: After swapping, the code adds the left and right sub-trees of the current node to the end of the queue. This is like adding the people standing behind the current person to the end of the line. It ensures that the newly swapped nodes will be processed in the next iteration.

6. Continuing the Loop: The loop continues, and the process repeats for the next item in the queue. This continues until the queue is empty, and all nodes in the binary tree have been processed and swapped.

By the time this function finishes running, the binary tree will be completely inverted, with the left and right branches swapped for every node.

It's a clever way to transform the structure of a tree, and it can be very useful in various programming and computer science tasks.