Invert Binary Tree easy

Problem Statement

Invert a binary tree.

For example, given the following binary tree:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

should be inverted to:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Example 1

Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Example 2

Input: root = [2,1,3] Output: [2,3,1]

Steps

1. Base Case: If the root is null, return null. This handles empty trees.

2. Recursive Step:

   • Swap the left and right children of the current node.
   • Recursively invert the left subtree (the original right subtree, now the left).
   • Recursively invert the right subtree (the original left subtree, now the right).

Explanation

The solution uses recursion. The core idea is to swap the left and right children at each node. By recursively inverting the left and right subtrees, we ensure that the entire tree is inverted. The base case (null root) stops the recursion when we reach the end of a branch. The algorithm works its way down the tree, swapping children at each node, and then recursively handles the subtrees until it reaches the leaves.

Code

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null; // Base case: empty tree
        }

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

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

        return root;
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H) in the worst case, where H is the height of the tree. This is due to the recursive call stack. In the best case (a balanced tree), H = log(N). In the worst case (a skewed tree), H = N.