deepSWE.io

Invert Binary Tree

TreeDFSRecursion

EasyLeetCode #226

5 min

Problem Statement

Given the root of a binary tree, invert the tree, and return its root.

Example

Example 1:

Input:

Output:

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 ≤ Node.val ≤ 100

Recursive Solution (DFS)

The recursive approach uses a Depth-First Search (DFS) strategy to traverse the tree and swap the left and right children of each node.

Algorithm Steps

The base case for the recursion is when a node is null, in which case we return null.
Recursively call the function on the left and right children.
Swap the left and right children of the current node.
Return the current node.

Start: Call invertTree on root (4).

Invert Binary Tree Solution


# 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]:
        # Base case: if the node is null, return null
        if not root:
            return None
        
        # Swap the left and right children
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        
        return root

Iterative Solution (BFS with Queue)

The iterative solution uses a queue to perform a Breadth-First Search (BFS). We traverse the tree level by level and swap the children of each node.

Algorithm Steps

If the root is null, return null.
Create a queue and add the root node.
While the queue is not empty, dequeue a node.
Swap the left and right children of the dequeued node.
If the left child is not null, add it to the queue.
If the right child is not null, add it to the queue.
After the loop, return the root.

Invert Binary Tree Solution


# 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
from collections import deque

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
            
        queue = deque([root])
        
        while queue:
            node = queue.popleft()
            
            # Swap the left and right children
            node.left, node.right = node.right, node.left
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        return root