Invert Binary Tree

Easytreedepth-first-searchrecursion
Category: Trees
Companies that ask this question:
GoogleAmazonFacebookMicrosoft
LeetCode →NeetCode →

Approach

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 all nodes in the tree.

Examples

Example 1

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

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

Example 2

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

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

Example 3

Input: root = []
Output: []

Intuition

Think about what "invert" means: every node's left child becomes its right child and vice versa.

We can solve this recursively:

  1. Swap the current node's left and right children
  2. Recursively invert the left subtree
  3. Recursively invert the right subtree

The base case is when we reach a null node (leaf's children), where we simply return null.

Pattern Recognition

This is a Tree Traversal + Recursion problem with:

  • Post-order or pre-order traversal (both work)
  • Simple recursive structure
  • Classic DFS pattern

Approach

Recursive Approach

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

The key insight is that we need to invert every single node in the tree, which naturally fits a recursive pattern.

Why this works:

  • Each recursive call handles one node's inversion
  • The recursion ensures we visit all nodes
  • Swapping happens at every level

Iterative Approach (Alternative)

We can also use a queue (BFS) or stack (DFS):

  1. Add root to queue
  2. While queue not empty:
    • Dequeue node
    • Swap its children
    • Enqueue both children (if not null)

Edge Cases

  • Empty tree (null root)
  • Single node tree
  • Tree with only left children
  • Tree with only right children
  • Perfectly balanced tree

Complexity Analysis

  • Time: O(n) where n = number of nodes

    • Visit each node exactly once
    • O(1) work per node (just swapping pointers)

  • Space: O(h) where h = height of tree

    • Recursion call stack depth
    • O(log n) for balanced tree, O(n) for skewed tree

Solution

java
1class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14class Solution {
15    public TreeNode invertTree(TreeNode root) {
16        // Base case: null node
17        if (root == null) {
18            return null;
19        }
20
21        // Swap left and right children
22        TreeNode temp = root.left;
23        root.left = root.right;
24        root.right = temp;
25
26        // Recursively invert subtrees
27        invertTree(root.left);
28        invertTree(root.right);
29
30        return root;
31    }
32}
33
Loading visualizer...