Invert Binary Tree

Recursive swap

The simplest recursive tree transformation. Swap left and right, recurse.

Published Apr 15, 2026

Problem

Given the root of a binary tree, invert the tree — swap the left and right children at every node — and return the root.

Input

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

Output

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

Explanation

Each node's children are swapped, recursively.

Intuition

Inverting a tree at a node means: swap the two subtrees, and make sure each subtree is itself inverted.

That sentence is already the algorithm. It's a textbook recursive definition — a node's inversion is defined in terms of its children's inversions. The base case is the empty subtree: there's nothing to invert; return it.

This is the simplest possible tree recursion, and that's why it matters. Every tree pattern — max depth, diameter, path sums — shares this shape: process a node using results from its children. The recursive version is the cleanest; the iterative version shows the shape from the other side.

Approach

Recursive

TimeO(n)

SpaceO(h)

Recommended

Recurse into both children, then swap their inverted results. h is the height of the tree — balanced trees give O(log n) stack depth, skewed trees give O(n).

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn invert_tree(
        root: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = &root {
            let mut n = node.borrow_mut();
            let left = n.left.take();
            let right = n.right.take();
            n.left = Self::invert_tree(right);
            n.right = Self::invert_tree(left);
        }
        root
    }
}

Rust · runnable

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

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

TypeScript · runnable

Iterative BFS

TimeO(n)

SpaceO(w)

Visit each node level-order using a queue; swap its children on the way through. w is the max width — O(n/2) in the worst case, so asymptotically O(n) but with a different constant and no recursion depth risk. Use this when you're worried about stack overflow on skewed trees.

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

impl Solution {
    pub fn invert_tree(
        root: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let mut queue: VecDeque<Rc<RefCell<TreeNode>>> = VecDeque::new();
        if let Some(r) = root.clone() {
            queue.push_back(r);
        }
        while let Some(node) = queue.pop_front() {
            let mut n = node.borrow_mut();
            std::mem::swap(&mut n.left, &mut n.right);
            if let Some(l) = &n.left {
                queue.push_back(l.clone());
            }
            if let Some(r) = &n.right {
                queue.push_back(r.clone());
            }
        }
        root
    }
}

Rust · runnable

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  const queue: TreeNode[] = [root];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++]!;
    [node.left, node.right] = [node.right, node.left];
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return root;
}

TypeScript · runnable

Trace

Recursive approach on root = [4, 2, 7, 1, 3, 6, 9]:

Before:           After:
    4                 4
   / \               / \
  2   7             7   2
 / \ / \           / \ / \
1  3 6  9         9  6 3  1

The recursion visits leaves first (bottom-up in effect), then swaps each subtree as it unwinds. BFS visits top-down, swapping before descending — different traversal order, identical result.

Edge cases

Empty tree — both approaches return null/None immediately.
Single node — no children to swap; returns the node unchanged.
Skewed tree — recursive stack is O(n). Iterative BFS is safe regardless of shape.

Takeaway

Every tree algorithm starts with the same sentence: "the answer at this node is some function of the answers from its children." Write the sentence first; the recursive implementation falls out. The iterative version trades a bit of boilerplate for stack safety — worth knowing, rarely needed for interview-sized inputs.

Easy#104

Maximum Depth of Binary Tree

1 + max(left_depth, right_depth). This IS the recursive template.

Easy#543

Diameter of Binary Tree

Key insight: the answer might not pass through the root. Track a global max.

Hard#124

Binary Tree Maximum Path Sum

Like diameter but with values. Return one-side max to parent, track global two-side max.