Invert Binary Tree - Java Solution

1. Introduction

This blog post is dedicated to a simple yet intriguing problem in binary tree algorithms - inverting a binary tree. Inverting a binary tree means swapping all its left and right child nodes. The problem is a good exercise in understanding tree manipulation and recursion.

Problem

Given the root of a binary tree, the task is to invert the tree, which involves swapping every left child with its right child, and then return the new root of the inverted tree.

2. Solution Steps

1. Traverse the tree using a recursive approach.

2. At each node, swap its left and right children.

3. Apply the same operation recursively to both children of the current node.

4. Continue the process until all nodes have been visited and their children swapped.

5. Return the root of the inverted tree.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class InvertBinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(7);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        TreeNode invertedRoot = invertTree(root);
        // Output can be verified through tree traversal methods
    }

    // Function to invert a binary tree
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert the left and right subtrees
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

Output:

The binary tree is inverted, and its root is returned. The structure can be verified through tree traversal methods.

Explanation:

1. invertTree: This function inverts a binary tree. For each node, it swaps the left and right children.

2. The inversion is applied recursively to both the left and right subtrees of the node.

3. The base case for the recursion is when a null node is encountered, indicating the leaf of the tree.

4. The function returns the root of the newly inverted tree.

5. The process transforms the tree in place, ensuring that each subtree is also inverted, resulting in a complete inversion of the original tree.