Invert Binary Tree easy

Problem Statement

Invert a binary tree.

Example:

Input:

 4

/
2 7 / \ /
1 3 6 9

Output:

 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. Recursive Approach: We'll use a recursive function to traverse the tree.
2. Base Case: If the node is null, we return null.
3. Recursive Step: For each node, we swap its left and right children. Then, we recursively call the function on the left and right subtrees.

Explanation

The core idea is to swap the left and right children of every node in the binary tree. This is done recursively. The recursive calls ensure that this swapping happens at every level of the tree. The base case (null node) prevents infinite recursion.

Code

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) {
        return null; // Base case: empty tree
    }

    // Swap left and right children
    const 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 case of a skewed tree, H can be equal to N. In a balanced tree, H is log(N). In the best case (a perfectly balanced tree), the space complexity is O(log N).