Invert Binary Tree - Practice Coding Problems

Invert Binary Tree - Problem

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

To invert a binary tree means to swap the left and right children of every node in the tree recursively.

The original tree structure is preserved, but all left children become right children and vice versa.

Input & Output

Example 1 — Basic Binary Tree

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

› Output: [4,7,2,9,6,3,1]

💡 Note: The tree is inverted by swapping left and right children at every node. Root 4 stays same, but its children 2 and 7 swap positions, and recursively all subtrees are inverted.

Example 2 — Single Node

$ Input: root = [2]

› Output: [2]

💡 Note: A single node tree remains unchanged as there are no children to swap.

Example 3 — Empty Tree

$ Input: root = []

› Output: []

💡 Note: 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

Visualization

Tap to expand

Understanding the Visualization

Original Tree

Binary tree with values [4,2,7,1,3,6,9]

Swap Process

Recursively swap left and right children at each node

Inverted Result

Final tree with values [4,7,2,9,6,3,1]

Key Takeaway

🎯 Key Insight: Simply swap left and right children at every node recursively to mirror the tree

Asked in

G Google 45 a Amazon 38 M Microsoft 32 🍎 Apple 28

The key insight is that inverting a binary tree is simply swapping left and right children at every node. The optimal approach uses recursive DFS with clean code, though iterative BFS works too. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Iterative BFS	O(n)	O(w)	Use a queue to process nodes level by level, swapping children
Recursive DFS (Brute Force)	O(n)	O(h)	Recursively swap left and right children of each node

Iterative BFS — Algorithm Steps

Step 1: Initialize queue with root node
Step 2: While queue not empty, dequeue node and swap its children
Step 3: Add non-null children to queue for processing

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Add root to queue

Process Level

Dequeue node, swap children, enqueue children

Continue

Repeat until queue is empty

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* solution(struct TreeNode* root) {
    if (!root) return NULL;
    
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        
        // Swap left and right children
        struct TreeNode* temp = node->left;
        node->left = node->right;
        node->right = temp;
        
        // Add children to queue if they exist
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
    
    return root;
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void printArray(struct TreeNode* root) {
    if (!root) {
        printf("[]\n");
        return;
    }
    
    // Simple level order traversal for output
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    int values[1000];
    int count = 0;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        if (node) {
            values[count++] = node->val;
            queue[rear++] = node->left;
            queue[rear++] = node->right;
        }
    }
    
    printf("[");
    for (int i = 0; i < count; i++) {
        if (i > 0) printf(",");
        printf("%d", values[i]);
    }
    printf("]\n");
}

int main() {
    // For simplicity, create a small test case
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(7);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(6);
    root->right->right = createNode(9);
    
    struct TreeNode* result = solution(root);
    printArray(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once to swap its children

✓ Linear Growth

Space Complexity

O(w)

Queue stores nodes at current level, maximum width w of tree

✓ Linear Space

306.0K Views

High Frequency

~10 min Avg. Time

8.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Iterative BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler