226. Invert Binary Tree

Intuition

The problem requires swapping the left and right children of all nodes in the binary tree. This can be efficiently achieved using a recursive approach where we swap the children of each node and then recursively apply the same operation to the left and right subtrees.

Approach

1. Base Case: - If the current node (root) is None, return immediately as there's nothing to invert.
2. Swap Children: - Swap the left and right children of the current node.
3. Recursive Inversion: - Recursively call the inversion function on the left child of the current node. - Recursively call the inversion function on the right child of the current node.
4. Return Root: - Return the root of the tree after inverting all its nodes.

The recursive approach ensures that every node's children are swapped, effectively inverting the entire tree.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the binary tree. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).

Code

C++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        helper(root);
        return root;
    }
private:
    void helper(TreeNode* root) {
        if (root == nullptr) return;

        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        helper(root->left);
        helper(root->right);
    }
};

Python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.helper(root)
        return root

    def helper(self, root: Optional[TreeNode]):
        if root is None:
            return
        root.left, root.right = root.right, root.left

        # Recursively invert the left and right subtrees
        self.helper(root.left)
        self.helper(root.right)

Java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        helper(root);
        return root;
    }
    private void helper(TreeNode root) {
        if (root == null) return;

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        helper(root.left);
        helper(root.right);
    }
}

JavaScript

var invertTree = function(root) {
    helper(root);
    return root;
};
function helper(root){
    if(root == null) return;

    let temp = root.left;
    root.left = root.right;
    root.right = temp;

    helper(root.left);
    helper(root.right);
}