Invert Binary Tree

Easy
1868.

Invert Binary Tree

Invert Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary tree, invert it — swap the left and right children of every node, producing the tree's mirror image — and return its root.

Example 1

Input
root = [4,2,7,1,3,6,9]
Output
[4,7,2,9,6,3,1]
Explanation
Every level now reads right to left.

Example 2

Input
root = [2,1]
Output
[2,null,1]
Explanation
The single left child becomes a right child.

Example 3

Input
root = []
Output
[]

Constraints

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Invert Binary Tree — Solution in Python, Java & C++

Invert Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Invert Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary tree, invert it — swap the left and right children of every node, producing the tree's mirror image — and return its root.

Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation: Every level now reads right to left.

Example 2

Input: root = [2,1]
Output: [2,null,1]
Explanation: The single left child becomes a right child.

Example 3

Input: root = []
Output: []

Constraints

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

Hints for Invert Binary Tree

  1. Hint 1

    Inverting a tree means inverting both subtrees and then swapping them.

  2. Hint 2

    Write it as a recursion whose base case is the empty tree.

  3. Hint 3

    Any traversal order works as long as every node has its two child pointers swapped exactly once — a BFS queue does it iteratively.

How to solve Invert Binary Tree

The mirror of a tree is its root with the mirror of the right subtree on the left and the mirror of the left subtree on the right. Swapping the two child pointers at every node, in any order, builds exactly that.

Approach

  1. If root is null, return null.
  2. Invert the left and right subtrees recursively.
  3. Assign the inverted right subtree to root.left and the inverted left subtree to root.right.
  4. Return root.

Why it works

By induction on height: the recursive calls return mirrored subtrees, and placing them on the opposite sides mirrors the whole tree. Each node is visited once and its pointers swapped once, so nothing is swapped back.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth

Pitfalls

  • Overwriting root.left before saving it loses the left subtree — keep one side in a temporary.
  • Swapping a node's pointers twice (for example, once on the way down and once on the way up) undoes the inversion.

Reference solution

Python

from typing import Optional

def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

Java

public static TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode l = invertTree(root.left);
    root.left = invertTree(root.right);
    root.right = l;
    return root;
}

C++

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    TreeNode* l = invertTree(root->left);
    root->left = invertTree(root->right);
    root->right = l;
    return root;
}

JavaScript

var invertTree = function(root) {
    if (root === null) return null;
    var l = invertTree(root.left);
    root.left = invertTree(root.right);
    root.right = l;
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)