Invert Binary Tree

The problem asks you to mirror a binary tree, effectively swapping the left and right children of each node. This tests your understanding of tree traversals and recursion, crucial for many tree-based algorithms.

treerecursionbinary treedepth-first searchin-place

Problem Statement

Given the root of a binary tree, modify the tree in-place such that the left and right subtrees of every node are swapped. Return the root of the modified tree, which should now be the mirror image of the original tree.

Example 1

Input: A binary tree with root 4, left child 2 (with children 1 and 3), and right child 7 (with children 6 and 9).

Output: A binary tree with root 4, left child 7 (with children 9 and 6), and right child 2 (with children 3 and 1).

The original tree is mirrored by swapping the left and right children at each level. For example, the left subtree rooted at 2 becomes the right subtree, and vice versa. The nodes within each subtree also maintain their mirrored relationship.

Example 2

Input: A binary tree with root 1, left child 5, and no right child.

Output: A binary tree with root 1, right child 5, and no left child.

Since there is no right child in the original tree, the left child (5) becomes the right child after mirroring. The left child becomes None.

Constraints

-The number of nodes in the tree is in the range [0, 100].
-Each node's value is an integer in the range [0, 100].
-The input is the root node of a valid binary tree.

Brute Force Approach

The brute force approach would be like manually redrawing the entire tree on a new sheet of paper, but mirroring the connections as you go. For each node, you'd create a new node in the mirrored position and connect it to the mirrored children. This creates a completely new tree.

TimeO(n)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem