Invert Binary Tree

Inverting a binary tree means that the left and right children of all nodes are swapped. Here’s a simple recursive solution to invert a binary tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None

        # Swap left and right children
        root.left, root.right = root.right, root.left

        # Invert the left and right subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

The idea here is to recursively invert the left and right subtrees and then swap them. The base case is when you reach a None node, in which case there’s nothing to invert. The method returns the root of the inverted tree.

The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree, as each node is visited once.

Binary tree swap equivalent of Array swap

  1. Left subtree has become the rigth subtree
  2. It keeps propagating to all the nodes below
  3. What is the unit of work? root.right becomes root.left root.left becomes root.right
  4. Should we do it in place or make a copy? Exchange it in place Save the reference before exchange
  5. What is the base case?
    • Empty tree - nil => return
    • Leaf node => return
  6. Define the interface Input : Root reference Output : Root reference
  7. Where do we do the unit of work?
    • We need the left and right child
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root
# @return {TreeNode}

def invert_tree(root)
    if root.nil?
        return
    end

    left_subtree = root.left
    right_subtree = root.right

    root.left = right_subtree
    root.right = left_subtree

    invert_tree(root.left)
    invert_tree(root.right)

    return root
end

Identifying Problem Isomorphism

“Invert Binary Tree” has an approximate mapping to “Symmetric Tree”. Both problems deal with the structure and symmetry of binary trees.

In “Invert Binary Tree”, you have to invert a binary tree, meaning that for each node in an original tree, its left child becomes its right child and vice versa.

In “Symmetric Tree”, you have to check if a binary tree is mirror symmetric, i.e., the left subtree of a node is a mirror reflection of its right subtree.

The main reason these two problems are similar is that they both require a deep understanding of binary tree structure, recursion, and the mirror concept. In “Invert Binary Tree”, you create a mirror of the original tree, while in “Symmetric Tree”, you check if the tree is its own mirror.

“Symmetric Tree” is simpler problem as it only requires a check for symmetry, whereas “Invert Binary Tree” requires the creation of a new tree structure.

1
2
3
4
5
6
7
8
9

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: 
            return root
        self.invertTree(root.left) 
        self.invertTree(root.right)  

        root.left, root.right = root.right, root.left
        return root

Problem Classification

  1. Data Structures: The problem involves working with a specific type of data structure - a Binary Tree.

  2. Tree Traversal: The problem requires navigating through a binary tree, suggesting that it involves concepts related to tree traversal.

  3. Recursion: The operation must be performed for all nodes in the tree, suggesting a recursive solution is likely.

  4. In-place Algorithms: The problem requires the tree to be modified directly (the left and right child of each node is being swapped), suggesting that it is an in-place algorithm problem.

So, this problem primarily falls into the domain trees, tree traversal, recursion, and in-place algorithms.

Language Agnostic Coding Drills

This involves inverting a binary tree. The steps involved here can be broken down into the following learning units or drills:

  1. Understanding Binary Trees: You need to understand what binary trees are, their properties, and how they are used.

  2. Tree Traversal: It’s necessary to understand the concept of tree traversal, particularly depth-first search (DFS), as this problem involves recursive traversal of the tree nodes. There are different types of DFS - Preorder, Inorder and Postorder. The particular type used in this problem is postorder DFS.

  3. Recursion: You need to understand how to use recursion to solve problems that involve repeating structures, such as trees. Recursion is a key concept in solving many tree-based problems, including this one.

  4. Working with Tree Nodes: Understand how to work with individual nodes in a tree, including accessing the node’s data and its left and right children. You should be able to create, read, update, and delete nodes.

  5. In-place Operations: Learn how to make changes to the data structure in-place, i.e., without creating a new copy of the data structure. In this problem, we are asked to invert the tree in-place.

Problem Solving Approach:

  1. We first understand the problem statement and realize that we have to invert the binary tree. This means that for each node in the binary tree, we have to swap its left and right children.

  2. We choose a depth-first search strategy to traverse the tree. We use recursion to implement this.

  3. We check if the root node is null. If it is, we return as there’s nothing to invert.

  4. We then recursively invert the left subtree and the right subtree.

  5. After the left and right subtrees are inverted, we swap the left and right child of the current root node.

  6. Finally, we return the root of the inverted tree.

This is a recursive process that eventually inverts the entire tree.

Targeted Drills in Python

1. Understanding Binary Trees

For this concept, we can create a simple binary tree. Here, I am using the TreeNode class typically provided in LeetCode problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

2. Tree Traversal (DFS)

For this drill, let’s implement a simple post-order traversal (left, right, root):

1
2
3
4
5
6
7

def postorder_traversal(root):
    if root is not None:
        postorder_traversal(root.left)
        postorder_traversal(root.right)
        print(root.val)
        
postorder_traversal(root)

3. Recursion

Let’s create a simple recursive function to calculate the factorial of a number:

1
2
3
4
5
6
7

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

4. Working with Tree Nodes

This concept is a part of all the other drills. We create nodes in the first drill, traverse them in the second, and will swap them in the next drill.

5. In-place Operations

Now let’s try a problem-specific drill. We will write a function to swap the left and right children of every node in a binary tree:

1
2
3
4
5
6
7

def swap_children(root):
    if root is not None:
        root.left, root.right = root.right, root.left
        swap_children(root.left)
        swap_children(root.right)

swap_children(root)

Integrated Drill:

Finally, the problem solution is a combination of these drills: the creation of a binary tree (from the first drill), the recursive tree traversal (from the second and third drills), and the swapping operation (from the last drill). Combining them will lead to the problem’s solution.