SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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);
}