Skip to main content

🟩 Invert Binary Tree (#226)

🔗 Problem Link​

📋 Problem Statement​

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

💡 Examples​

Example 1​

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2​

Input: root = [2,1,3]
Output: [2,3,1]

Example 3​

Input: root = []
Output: []

🔑 Key Insights & Approach​

Core Observation: Swap left and right children recursively for each node.

Why Recursion?

  • Natural fit for tree structure
  • O(n) time, O(h) space for recursion stack
  • Clean and concise

Approaches:

  1. Recursive DFS: O(n) time, O(h) space - clean
  2. Iterative BFS: O(n) time, O(n) space
  3. Iterative DFS: O(n) time, O(h) space

Pattern: "Tree Traversal with Swap" pattern.

🐍 Solution: Python​

Approach 1: Recursive​

Time Complexity: O(n) | Space Complexity: O(h)

from typing import Optional

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]:
        if not root:
            return None

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

        # Recursively invert subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

Approach 2: Iterative BFS​

Time Complexity: O(n) | Space Complexity: O(n)

from collections import deque
from typing import Optional

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

        queue = deque([root])

        while queue:
            node = queue.popleft()

            # Swap 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

🔵 Solution: Golang​

Approach: Recursive​

Time Complexity: O(n) | Space Complexity: O(h)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    // Swap children
    root.Left, root.Right = root.Right, root.Left

    // Recursively invert
    invertTree(root.Left)
    invertTree(root.Right)

    return root
}

📚 References​