Invert Binary Tree

1 min readUpdated 3 June 2025

Problem Statement

The task is to invert a binary tree by swapping the left and right child of every node, starting from the root down to the leaves. The input represents the root of a binary tree, and the goal is to return the root of the inverted tree. This operation reflects the entire structure of the tree across its vertical axis.

Examples

Example 1

Input:

EXAMPLE_ENTITY

root = [4,2,7,1,3,6,9]

Output:

EXAMPLE_ENTITY

[4,7,2,9,6,3,1]

Explanation:

EXAMPLE_ENTITY

Swapping all left and right children results in:
    Original:         Inverted:
        4                 4
       / \               / \
      2   7     -->     7   2
     / \ / \           / \ / \
    1  3 6  9         9  6 3  1

Example 2

Input:

EXAMPLE_ENTITY

root = [2,1,3]

Output:

EXAMPLE_ENTITY

[2,3,1]

Explanation:

EXAMPLE_ENTITY

Swapping 1 and 3 results in a mirrored structure of the original tree.

Example 3

Input:

EXAMPLE_ENTITY

root = []

Output:

EXAMPLE_ENTITY

[]

Explanation:

EXAMPLE_ENTITY

An empty tree remains empty after inversion.

Constraints

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

Approach and Intuition

To invert the tree, the core idea is to recursively or iteratively swap the left and right children of each node.

Recursive Approach

Base Case: If the current node is null, return null.
Recursively invert the left and right subtrees.
Swap the left and right children.
Return the current node.

This is simple and elegant for most tree sizes.

Iterative Approach (Queue or Stack)

Use a queue (for BFS) or a stack (for DFS) to traverse nodes level-by-level or depth-first.
For each node:
- Swap its left and right children.
- Push the non-null children into the queue or stack.
Repeat until all nodes are processed.

Time and Space Complexity

Time Complexity: O(n) — Every node is visited once.
Space Complexity: O(h) for recursion, where h is the height of the tree; O(n) for iterative methods using a queue or stack.

This inversion technique is useful in problems involving mirrored structures or graphical transformations of trees.

Solutions

JAVA
class Solution {
    public TreeNode reverseTree(TreeNode rootNode) {
        if (rootNode == null) return null;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.add(rootNode);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            TreeNode swapHolder = node.left;
            node.left = node.right;
            node.right = swapHolder;
            if (node.left != null) nodeQueue.add(node.left);
            if (node.right != null) nodeQueue.add(node.right);
        }
        return rootNode;
    }
}
Powered by Vultr AgentBeta

The problem requires you to invert a binary tree, and the provided Java solution successfully achieves this using a breadth-first search approach. The solution defines a method reverseTree that accepts the root node of a binary tree and returns the root of the inverted tree.

Here's how the solution works:

Check if the input rootNode is null. If so, return null immediately, indicating there's nothing to invert.
Initialize a Queue to keep track of the tree nodes, ensuring each node and its children are processed in a level-order manner (breadth-first).
Add the rootNode to the queue as the starting point of the tree traversal.
Execute a loop as long as the queue is not empty. During each iteration of the loop:
- Remove the front node from the queue using poll() and store it in a variable node.
- Swap the left and right children of the current node.
- Store the right child in a temporary variable swapHolder before the swap to facilitate easy swapping.
- After swapping, if the left child of node is not null, add it to the queue to process its children in subsequent iterations.
- Similarly, add the right child of node to the queue if it is not null.
After the loop completes, all nodes of the tree will have their children inverted, and the method returns the modified rootNode, now representing the root of the inverted tree.

This solution leverages a queue to ensure the tree is traversed level by level and swaps children of each node to invert the binary tree successfully. The reverseTree method modifies the tree in-place and returns the root of the newly inverted tree, ready for further operations or checks as needed.

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Invert Binary Tree

1 min readUpdated 3 June 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

root = [4,2,7,1,3,6,9]

Output:

EXAMPLE_ENTITY

[4,7,2,9,6,3,1]

Explanation:

EXAMPLE_ENTITY

Swapping all left and right children results in:
    Original:         Inverted:
        4                 4
       / \               / \
      2   7     -->     7   2
     / \ / \           / \ / \
    1  3 6  9         9  6 3  1

Example 2

Input:

EXAMPLE_ENTITY

root = [2,1,3]

Output:

EXAMPLE_ENTITY

[2,3,1]

Explanation:

EXAMPLE_ENTITY

Swapping 1 and 3 results in a mirrored structure of the original tree.

Example 3

Input:

EXAMPLE_ENTITY

root = []

Output:

EXAMPLE_ENTITY

[]

Explanation:

EXAMPLE_ENTITY

An empty tree remains empty after inversion.

Constraints

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

Approach and Intuition

To invert the tree, the core idea is to recursively or iteratively swap the left and right children of each node.

Recursive Approach

Base Case: If the current node is null, return null.
Recursively invert the left and right subtrees.
Swap the left and right children.
Return the current node.

This is simple and elegant for most tree sizes.

Iterative Approach (Queue or Stack)

Use a queue (for BFS) or a stack (for DFS) to traverse nodes level-by-level or depth-first.
For each node:
- Swap its left and right children.
- Push the non-null children into the queue or stack.
Repeat until all nodes are processed.

Time and Space Complexity

Time Complexity: O(n) — Every node is visited once.
Space Complexity: O(h) for recursion, where h is the height of the tree; O(n) for iterative methods using a queue or stack.

This inversion technique is useful in problems involving mirrored structures or graphical transformations of trees.

Solutions

JAVA
class Solution {
    public TreeNode reverseTree(TreeNode rootNode) {
        if (rootNode == null) return null;
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        nodeQueue.add(rootNode);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();
            TreeNode swapHolder = node.left;
            node.left = node.right;
            node.right = swapHolder;
            if (node.left != null) nodeQueue.add(node.left);
            if (node.right != null) nodeQueue.add(node.right);
        }
        return rootNode;
    }
}
Powered by Vultr AgentBeta

Here's how the solution works:

Check if the input rootNode is null. If so, return null immediately, indicating there's nothing to invert.
Initialize a Queue to keep track of the tree nodes, ensuring each node and its children are processed in a level-order manner (breadth-first).
Add the rootNode to the queue as the starting point of the tree traversal.
Execute a loop as long as the queue is not empty. During each iteration of the loop:
- Remove the front node from the queue using poll() and store it in a variable node.
- Swap the left and right children of the current node.
- Store the right child in a temporary variable swapHolder before the swap to facilitate easy swapping.
- After swapping, if the left child of node is not null, add it to the queue to process its children in subsequent iterations.
- Similarly, add the right child of node to the queue if it is not null.
After the loop completes, all nodes of the tree will have their children inverted, and the method returns the modified rootNode, now representing the root of the inverted tree.

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.