Invert Binary Tree

Problem Statement

Given the root of a binary tree, invert the tree, and return its root. Inverting a binary tree means swapping the left and right children of every node in the tree.

Input:

• Root of a binary tree

Output:

• Root of the inverted binary tree

Constraints:

• The number of nodes in the tree is in the range 0, 100
• -100 ≤ Node.val ≤ 100

Examples:

Example 1:

Original:     Inverted:
    4             4
   / \           / \
  2   7         7   2
 / \ / \       / \ / \
1  3 6  9     9  6 3  1

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

Example 2:

Original:  Inverted:
   2          2
  / \        / \
 1   3      3   1

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Example 4:

Input: root = [1]
Output: [1]

Solutions

Approach 1: Recursive Solution

Use recursion to invert the tree by swapping left and right children at each node.

Algorithm:

1. Base case: if node is null, return null
2. Swap the left and right children of current node
3. Recursively invert the left and right subtrees
4. Return the current node

Python:

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

def invertTree(root):
    """
    Recursive approach to invert binary tree
    Time: O(N) where N is number of nodes
    Space: O(H) where H is height of tree (recursion stack)
    """
    if not root:
        return None
    
    # Swap left and right children
    root.left, root.right = root.right, root.left
    
    # Recursively invert subtrees
    invertTree(root.left)
    invertTree(root.right)
    
    return root

def invertTreePostOrder(root):
    """
    Post-order approach: invert children first, then swap
    Time: O(N)
    Space: O(H)
    """
    if not root:
        return None
    
    # First invert the subtrees
    left = invertTreePostOrder(root.left)
    right = invertTreePostOrder(root.right)
    
    # Then swap the children
    root.left = right
    root.right = left
    
    return root

def invertTreeCompact(root):
    """
    Most compact recursive solution
    Time: O(N)
    Space: O(H)
    """
    if root:
        root.left, root.right = invertTreeCompact(root.right), invertTreeCompact(root.left)
    return root

Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /**
     * Recursive approach to invert binary tree
     * Time: O(N)
     * Space: O(H)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        // Swap left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert subtrees
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
    
    /**
     * Post-order approach: invert children first, then swap
     * Time: O(N)
     * Space: O(H)
     */
    public TreeNode invertTreePostOrder(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        // First invert the subtrees
        TreeNode left = invertTreePostOrder(root.left);
        TreeNode right = invertTreePostOrder(root.right);
        
        // Then swap the children
        root.left = right;
        root.right = left;
        
        return root;
    }
    
    /**
     * Most compact recursive solution
     * Time: O(N)
     * Space: O(H)
     */
    public TreeNode invertTreeCompact(TreeNode root) {
        if (root != null) {
            TreeNode temp = invertTreeCompact(root.left);
            root.left = invertTreeCompact(root.right);
            root.right = temp;
        }
        return root;
    }
}

Go:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// invertTree - Recursive approach to invert binary tree
// Time: O(N)
// Space: O(H)
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    // Swap left and right children
    root.Left, root.Right = root.Right, root.Left
    
    // Recursively invert subtrees
    invertTree(root.Left)
    invertTree(root.Right)
    
    return root
}

// invertTreePostOrder - Post-order approach
// Time: O(N)
// Space: O(H)
func invertTreePostOrder(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    // First invert the subtrees
    left := invertTreePostOrder(root.Left)
    right := invertTreePostOrder(root.Right)
    
    // Then swap the children
    root.Left = right
    root.Right = left
    
    return root
}

// invertTreeCompact - Most compact recursive solution
// Time: O(N)
// Space: O(H)
func invertTreeCompact(root *TreeNode) *TreeNode {
    if root != nil {
        root.Left, root.Right = invertTreeCompact(root.Right), invertTreeCompact(root.Left)
    }
    return root
}

JavaScript:

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

/**
 * Recursive approach to invert binary tree
 * Time: O(N)
 * Space: O(H)
 */
function invertTree(root) {
    if (!root) {
        return null;
    }
    
    // Swap left and right children
    [root.left, root.right] = [root.right, root.left];
    
    // Recursively invert subtrees
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

/**
 * Post-order approach: invert children first, then swap
 * Time: O(N)
 * Space: O(H)
 */
function invertTreePostOrder(root) {
    if (!root) {
        return null;
    }
    
    // First invert the subtrees
    const left = invertTreePostOrder(root.left);
    const right = invertTreePostOrder(root.right);
    
    // Then swap the children
    root.left = right;
    root.right = left;
    
    return root;
}

/**
 * Most compact recursive solution
 * Time: O(N)
 * Space: O(H)
 */
function invertTreeCompact(root) {
    if (root) {
        [root.left, root.right] = [invertTreeCompact(root.right), invertTreeCompact(root.left)];
    }
    return root;
}

C#:

using System;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    /// <summary>
    /// Recursive approach to invert binary tree
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        // Swap left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert subtrees
        InvertTree(root.left);
        InvertTree(root.right);
        
        return root;
    }
    
    /// <summary>
    /// Post-order approach: invert children first, then swap
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    public TreeNode InvertTreePostOrder(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        // First invert the subtrees
        TreeNode left = InvertTreePostOrder(root.left);
        TreeNode right = InvertTreePostOrder(root.right);
        
        // Then swap the children
        root.left = right;
        root.right = left;
        
        return root;
    }
    
    /// <summary>
    /// Most compact recursive solution
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    public TreeNode InvertTreeCompact(TreeNode root) {
        if (root != null) {
            TreeNode temp = InvertTreeCompact(root.left);
            root.left = InvertTreeCompact(root.right);
            root.right = temp;
        }
        return root;
    }
}

Approach 2: Iterative Solution using Stack (DFS)

Use an explicit stack to perform depth-first traversal and invert nodes.

Algorithm:

1. Use a stack to track nodes to process
2. Push root onto stack
3. While stack is not empty:
   • Pop a node
   • Swap its left and right children
   • Push non-null children onto stack

Python:

def invertTreeIterative(root):
    """
    Iterative approach using stack (DFS)
    Time: O(N)
    Space: O(H)
    """
    if not root:
        return None
    
    stack = [root]
    
    while stack:
        node = stack.pop()
        
        # Swap left and right children
        node.left, node.right = node.right, node.left
        
        # Add children to stack for processing
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return root

def invertTreePreOrder(root):
    """
    Iterative pre-order traversal approach
    Time: O(N)
    Space: O(H)
    """
    if not root:
        return None
    
    stack = [root]
    
    while stack:
        node = stack.pop()
        
        # Process current node (swap children)
        node.left, node.right = node.right, node.left
        
        # Add children in reverse order for pre-order
        if node.right:  # This was originally left
            stack.append(node.right)
        if node.left:   # This was originally right
            stack.append(node.left)
    
    return root

Java:

import java.util.Stack;

public TreeNode invertTreeIterative(TreeNode root) {
    /**
     * Iterative approach using stack (DFS)
     * Time: O(N)
     * Space: O(H)
     */
    if (root == null) {
        return null;
    }
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        
        // Swap left and right children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Add children to stack for processing
        if (node.left != null) {
            stack.push(node.left);
        }
        if (node.right != null) {
            stack.push(node.right);
        }
    }
    
    return root;
}

public TreeNode invertTreePreOrder(TreeNode root) {
    /**
     * Iterative pre-order traversal approach
     * Time: O(N)
     * Space: O(H)
     */
    if (root == null) {
        return null;
    }
    
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        
        // Process current node (swap children)
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Add children in reverse order for pre-order
        if (node.right != null) {  // This was originally left
            stack.push(node.right);
        }
        if (node.left != null) {   // This was originally right
            stack.push(node.left);
        }
    }
    
    return root;
}

Go:

// invertTreeIterative - Iterative approach using stack (DFS)
// Time: O(N)
// Space: O(H)
func invertTreeIterative(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    stack := []*TreeNode{root}
    
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        // Swap left and right children
        node.Left, node.Right = node.Right, node.Left
        
        // Add children to stack for processing
        if node.Left != nil {
            stack = append(stack, node.Left)
        }
        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }
    
    return root
}

// invertTreePreOrder - Iterative pre-order traversal approach
// Time: O(N)
// Space: O(H)
func invertTreePreOrder(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    stack := []*TreeNode{root}
    
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        
        // Process current node (swap children)
        node.Left, node.Right = node.Right, node.Left
        
        // Add children in reverse order for pre-order
        if node.Right != nil {  // This was originally left
            stack = append(stack, node.Right)
        }
        if node.Left != nil {   // This was originally right
            stack = append(stack, node.Left)
        }
    }
    
    return root
}

JavaScript:

/**
 * Iterative approach using stack (DFS)
 * Time: O(N)
 * Space: O(H)
 */
function invertTreeIterative(root) {
    if (!root) {
        return null;
    }
    
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        // Swap left and right children
        [node.left, node.right] = [node.right, node.left];
        
        // Add children to stack for processing
        if (node.left) {
            stack.push(node.left);
        }
        if (node.right) {
            stack.push(node.right);
        }
    }
    
    return root;
}

/**
 * Iterative pre-order traversal approach
 * Time: O(N)
 * Space: O(H)
 */
function invertTreePreOrder(root) {
    if (!root) {
        return null;
    }
    
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        
        // Process current node (swap children)
        [node.left, node.right] = [node.right, node.left];
        
        // Add children in reverse order for pre-order
        if (node.right) {  // This was originally left
            stack.push(node.right);
        }
        if (node.left) {   // This was originally right
            stack.push(node.left);
        }
    }
    
    return root;
}

C#:

using System.Collections.Generic;

public TreeNode InvertTreeIterative(TreeNode root) {
    /// <summary>
    /// Iterative approach using stack (DFS)
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    if (root == null) {
        return null;
    }
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.Push(root);
    
    while (stack.Count > 0) {
        TreeNode node = stack.Pop();
        
        // Swap left and right children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Add children to stack for processing
        if (node.left != null) {
            stack.Push(node.left);
        }
        if (node.right != null) {
            stack.Push(node.right);
        }
    }
    
    return root;
}

public TreeNode InvertTreePreOrder(TreeNode root) {
    /// <summary>
    /// Iterative pre-order traversal approach
    /// Time: O(N)
    /// Space: O(H)
    /// </summary>
    if (root == null) {
        return null;
    }
    
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.Push(root);
    
    while (stack.Count > 0) {
        TreeNode node = stack.Pop();
        
        // Process current node (swap children)
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Add children in reverse order for pre-order
        if (node.right != null) {  // This was originally left
            stack.Push(node.right);
        }
        if (node.left != null) {   // This was originally right
            stack.Push(node.left);
        }
    }
    
    return root;
}

Approach 3: Iterative Solution using Queue (BFS)

Use level-order traversal (BFS) to invert the tree level by level.

Python:

from collections import deque

def invertTreeBFS(root):
    """
    Iterative BFS approach using queue
    Time: O(N)
    Space: O(W) where W is maximum width of tree
    """
    if not root:
        return None
    
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        # Swap left and right children
        node.left, node.right = node.right, node.left
        
        # Add children to queue for processing
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return root

def invertTreeLevelOrder(root):
    """
    Level-order approach that processes entire levels
    Time: O(N)
    Space: O(W)
    """
    if not root:
        return None
    
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        
        # Process entire level
        for _ in range(level_size):
            node = queue.popleft()
            
            # Swap children
            node.left, node.right = node.right, node.left
            
            # Add next level nodes
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return root

Java:

import java.util.Queue;
import java.util.LinkedList;

public TreeNode invertTreeBFS(TreeNode root) {
    /**
     * Iterative BFS approach using queue
     * Time: O(N)
     * Space: O(W) where W is maximum width
     */
    if (root == null) {
        return null;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        
        // Swap left and right children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Add children to queue for processing
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    
    return root;
}

public TreeNode invertTreeLevelOrder(TreeNode root) {
    /**
     * Level-order approach that processes entire levels
     * Time: O(N)
     * Space: O(W)
     */
    if (root == null) {
        return null;
    }
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        
        // Process entire level
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            
            // Swap children
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            
            // Add next level nodes
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    
    return root;
}

Go:

// invertTreeBFS - Iterative BFS approach using queue
// Time: O(N)
// Space: O(W) where W is maximum width
func invertTreeBFS(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        
        // Swap left and right children
        node.Left, node.Right = node.Right, node.Left
        
        // Add children to queue for processing
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    
    return root
}

// invertTreeLevelOrder - Level-order approach that processes entire levels
// Time: O(N)
// Space: O(W)
func invertTreeLevelOrder(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        
        // Process entire level
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            // Swap children
            node.Left, node.Right = node.Right, node.Left
            
            // Add next level nodes
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    
    return root
}

JavaScript:

/**
 * Iterative BFS approach using queue
 * Time: O(N)
 * Space: O(W) where W is maximum width
 */
function invertTreeBFS(root) {
    if (!root) {
        return null;
    }
    
    const queue = [root];
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        // Swap left and right children
        [node.left, node.right] = [node.right, node.left];
        
        // Add children to queue for processing
        if (node.left) {
            queue.push(node.left);
        }
        if (node.right) {
            queue.push(node.right);
        }
    }
    
    return root;
}

/**
 * Level-order approach that processes entire levels
 * Time: O(N)
 * Space: O(W)
 */
function invertTreeLevelOrder(root) {
    if (!root) {
        return null;
    }
    
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        // Process entire level
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            // Swap children
            [node.left, node.right] = [node.right, node.left];
            
            // Add next level nodes
            if (node.left) {
                queue.push(node.left);
            }
            if (node.right) {
                queue.push(node.right);
            }
        }
    }
    
    return root;
}

C#:

using System.Collections.Generic;

public TreeNode InvertTreeBFS(TreeNode root) {
    /// <summary>
    /// Iterative BFS approach using queue
    /// Time: O(N)
    /// Space: O(W) where W is maximum width
    /// </summary>
    if (root == null) {
        return null;
    }
    
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    
    while (queue.Count > 0) {
        TreeNode node = queue.Dequeue();
        
        // Swap left and right children
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        
        // Add children to queue for processing
        if (node.left != null) {
            queue.Enqueue(node.left);
        }
        if (node.right != null) {
            queue.Enqueue(node.right);
        }
    }
    
    return root;
}

public TreeNode InvertTreeLevelOrder(TreeNode root) {
    /// <summary>
    /// Level-order approach that processes entire levels
    /// Time: O(N)
    /// Space: O(W)
    /// </summary>
    if (root == null) {
        return null;
    }
    
    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    
    while (queue.Count > 0) {
        int levelSize = queue.Count;
        
        // Process entire level
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.Dequeue();
            
            // Swap children
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            
            // Add next level nodes
            if (node.left != null) {
                queue.Enqueue(node.left);
            }
            if (node.right != null) {
                queue.Enqueue(node.right);
            }
        }
    }
    
    return root;
}

Key Insights

1. Simple Operation: Inverting only requires swapping left and right children at each node
2. Any Traversal Works: Preorder, postorder, level-order all work equally well
3. In-Place Operation: No additional nodes need to be created
4. Recursive vs Iterative: Both approaches have same time complexity but different space characteristics

Edge Cases

1. Empty tree: Return null
2. Single node: Return the node unchanged
3. Only left children: Becomes only right children
4. Only right children: Becomes only left children
5. Balanced tree: Remains balanced after inversion

Common Mistakes

1. Creating new nodes: Inverting should modify existing tree, not create new one
2. Forgetting base case: Not handling null nodes in recursion
3. Wrong swap logic: Not properly swapping the children
4. Stack overflow: Deep recursion on very unbalanced trees
5. Modifying during traversal: Incorrectly handling node references after swapping

Follow-up Questions

1. Double inversion: What happens if you invert a tree twice?
2. Check if inverted: Given two trees, check if one is inversion of other
3. Partial inversion: Invert only nodes at even/odd levels
4. Mirror check: Check if a tree is symmetric (mirror of itself)
5. Invert subtree: Invert only a specific subtree