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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Invert Binary Tree

Difficulty: Easy

Problem Description

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

Key Insights

  • Inverting a binary tree means swapping the left and right children of every node in the tree.
  • This problem can be solved using either Depth-First Search (DFS) or Breadth-First Search (BFS) approaches.
  • The base case for recursion is when the node is null, in which case we simply return null.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as we need to visit each node once. Space Complexity: O(h) - where h is the height of the tree, due to the recursion stack in the DFS approach.

Solution

To invert a binary tree, we can use a recursive approach. At each node, we will:

  1. Swap its left and right children.
  2. Recursively call the invert function on the left and right children.

This approach effectively traverses the entire tree while performing the necessary swaps.

Code Solutions

def invertTree(root):
    if root is None:
        return None
    # Swap the left and right children
    root.left, root.right = root.right, root.left
    # Recursively invert the left and right subtrees
    invertTree(root.left)
    invertTree(root.right)
    return root
← Back to All Questions