Invert Binary Tree - Leetcode Solution

The Invert Binary Tree problem on LeetCode is a relatively simple problem that involves swapping the left and right children of all nodes in a binary tree. Below is a detailed solution to this problem using recursive function calls.

Problem Statement: Invert a binary tree.

Example: Input:

 4

/
2 7 / \ /
1 3 6 9

Output:

 4

/
7 2 / \ /
9 6 3 1

Solution: The basic idea behind this problem is to use a recursive function to invert the left and right children of each node in the binary tree.

The first step in the recursive function is to check if the root is null or not. If the root is null, we simply return as there is no need to invert an empty tree.

If the root is not null, we then create a temporary variable to store the left child of the root. We then recursively call the invert function on the left child to invert all of its children. We do the same thing for the right child of the root.

After the recursive calls are complete, we then swap the left and right children of the root using the temporary variable created earlier.

Finally, we return the root of the inverted tree.

Here is the Python code to implement this solution:

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: TreeNode) -> TreeNode:
        if root is None:
            return None

        # Recursively invert children of left and right subtrees
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # Swap left and right children of current node
        root.left = right
        root.right = left

        return root

Note that we define a TreeNode class to represent the nodes in the binary tree, with each node having a value, a left child, and a right child.

We then define the Solution class which contains the invertTree function. This function takes in a root node of the binary tree as an argument and returns the root node of the inverted tree.

We start by checking if the root is null. If it is, we simply return null.

If the root is not null, we then recursively call the invertTree function on the left child of the root and store the result in a variable 'left'. We do the same thing for the right child of the root and store the result in a variable 'right'.

After the recursive calls are complete, we then swap the left and right children of the root using a temporary variable. Finally, we return the root of the inverted tree.

The time complexity of this solution is O(n) where n is the number of nodes in the binary tree since we visit each node once. The space complexity of this solution is also O(n) since we store the call stack for each recursive call.

1