Invert Binary Tree easy

Problem Statement

Invert a binary tree.

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]

Example 3:

Input: root = []
Output: []

Steps

1. Recursive Approach: We will use a recursive function to traverse the tree.
2. Base Case: If the current node is null, we return null (nothing to invert).
3. Recursive Step: For each node, we swap its left and right children. Then, we recursively call the invert function on the left and right subtrees.

Explanation

The inversion process involves swapping the left and right children of each node in the tree. This is done recursively. The recursion starts at the root and works its way down to the leaves. Each recursive call handles a subtree, swapping the children and then recursively inverting the left and right subtrees of that node. The base case is when we reach a null node (the end of a branch), at which point the recursion unwinds, and the swapped nodes propagate upwards to complete the inversion of the entire tree.

Code

using System;

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

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        // Base case: If the root is null, there's nothing to invert.
        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.
        root.left = InvertTree(root.left);
        root.right = InvertTree(root.right);

        // Return the inverted root.
        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), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In the best case (a balanced tree), H would be log₂(N). Therefore, the space complexity is O(H) which is O(N) in the worst case and O(log N) in the best case.