Leetcode - 226. Invert Binary Tree

Easy

Dec 23, 2025

#binary-tree

#bfs

226. Invert Binary Tree

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

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: []

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

Constraints:

Notes

Intuition

Inverting a tree means swapping every node's left and right children. We can traverse the tree using BFS (or DFS) and perform the swap at each node.

Implementation

Handle the empty tree case first. Initialize a queue with the root. For each node dequeued, swap its left and right children. Then enqueue any non-null children to continue the traversal. Return the original root reference (now pointing to the inverted tree).

Edge-cases

An empty tree (null root) should return null immediately. The algorithm handles single-node trees naturally.

Time: O(n) — visit each node once
Space: O(n) — queue holds up to n/2 nodes at the widest level

Complexity

Solution

from typing import Deque, Optional
from lcutils import TreeNode
from collections import deque

# 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]:
        if root is None:
            return root
        q: Deque[TreeNode] = deque([root])
        
        while q:
            node = q.popleft()
            node.right, node.left = node.right, node.left
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return root



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()