We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Invert Binary Tree

Number: 226

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Apple, Oracle, Bloomberg, Microsoft, TikTok

Problem Description

Given the root of a binary tree, invert the tree by swapping the left and right subtrees recursively, and return the root of the inverted tree.

Key Insights

  • The problem can be solved using recursion (depth-first search) by swapping the children of every node.
  • Alternatively, an iterative approach (using a queue for breadth-first search) can be used.
  • The recursion terminates when a null node is encountered.
  • The operation is performed in-place, modifying the original tree structure.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, since each node is visited once. Space Complexity: O(h) where h is the height of the tree, which is the recursion stack space in the recursive approach. In worst-case (skewed tree), this could be O(n).

Solution

We solve the problem using recursion (depth-first search). The approach is to:

  1. Check the base case: if the node is null, simply return null.
  2. Recursively invert the left subtree and the right subtree.
  3. Swap the left and right children of the current node.
  4. Return the current node after the swap. The recursive approach elegantly handles all nodes and ensures the inversion process covers the complete tree.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val        # Initialize node value
        self.left = left      # Pointer to left child
        self.right = right    # Pointer to right child

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # Base case: if the node is None, return None.
        if not root:
            return None
        # Recursively invert the left and right subtrees.
        left_inverted = self.invertTree(root.left)
        right_inverted = self.invertTree(root.right)
        # Swap the left and right children.
        root.left, root.right = right_inverted, left_inverted
        return root
← Back to All Questions