Domain 1EasyCORE

Invert Binary Tree

The problem requires us to invert a binary tree. Given the root of a binary tree, we need to swap every left child with its corresponding right child throughout the entire tree and return the root of the inverted tree.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

226. Invert Binary Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 67.3%


Problem Breakdown

The problem requires us to invert a binary tree. Given the root of a binary tree, we need to swap every left child with its corresponding right child throughout the entire tree and return the root of the inverted tree.

Inputs:

  • root: The root node of the binary tree.

Outputs:

  • The root node of the inverted binary tree.

Implicit Constraints or Tricky Edge Cases:

  • An empty tree (i.e., root is null).
  • A tree with only one node.
  • Trees where all nodes have both left and right children.

Intuition

A brute-force approach would involve traversing each node in the tree and manually swapping its left and right children. However, this approach is inefficient because it doesn’t take advantage of the recursive nature of trees.

The key insight is to use a recursive approach to invert the tree. By recursively inverting the left and right subtrees and then swapping them at each node, we can achieve the desired inversion efficiently.

Approach

We will use a recursive depth-first search (DFS) approach to traverse the tree. At each node, we:

  1. Recursively invert its left subtree.
  2. Recursively invert its right subtree.
  3. Swap the left and right children of the current node.
  4. Return the root node of the inverted tree.

This approach ensures that every node in the tree is visited once, and its children are swapped correctly.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case (a skewed tree), the space complexity can be O(n).

Solution

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

def invertTree(root: TreeNode) -> TreeNode:
    if root is None:
        return None
    
    # Recursively invert the left and right subtrees
    left_inverted = invertTree(root.left)
    right_inverted = invertTree(root.right)
    
    # Swap the left and right children
    root.left = right_inverted
    root.right = left_inverted
    
    return root

Edge Cases Handled

  • Empty Tree: If the input tree is empty (root is None), the function immediately returns None, which is correct for an inverted empty tree.
  • Single Node Tree: A tree with only one node remains unchanged after inversion since it has no children to swap.
  • Skewed Trees: The recursive approach handles skewed trees (completely unbalanced) efficiently, as each node is processed in constant time.