#3 · Trees

Invert Binary Tree

Given the root of a binary tree, invert it (swap every node's left and right children) and return its root.

EasyLeetCode

Current node
On the path / call stack
Done / found
Rejected
Temporary thread (Morris)

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary tree (pointer-based)

Each node holds a value and two child references. A subtree is identified by its root pointer, so moving a whole subtree is a single pointer assignment.

Memory layout

Nodes are separate heap objects linked by pointers. Traversal chases pointers (poor cache locality), but swapping two children touches only the parent node: O(1) regardless of subtree size.

Operation	Cost
visit all nodes	O(n)
swap two children	O(1)
DFS extra space	O(h): h = height; O(log n) balanced, O(n) skewed
BFS extra space	O(w): w = max width; up to ~n/2 for a perfect tree

Call stack / explicit stack / queue

The traversal order is driven by a LIFO stack (DFS, either implicit via recursion or explicit) or a FIFO queue (BFS).

Memory layout

The call stack holds one frame per active recursive call (return address, locals). An explicit stack is a growable heap array and is not bound by the thread's stack-size limit.

Operation	Cost
push / pop	O(1) amortized
array shift() as queue	O(n) in the worst case; use an index or a deque

Why it fits

Inversion is a local rule: "swap the two children at every node". Nodes are independent, so any traversal order that visits each node once is correct.
Pointer swaps are O(1) no matter how big the subtrees are, so the total cost is exactly one visit per node: Θ(n), which is optimal because every node must be inspected.
DFS fits the recursive shape of the tree and costs O(h) memory; BFS is the right pick when you want level order or want to avoid deep recursion on a wide tree.

Why alternatives degrade

Rebuilding the tree from a serialized form:: Costs O(n) extra memory and allocation for something the existing nodes already encode.
Array (heap-layout) representation:: Swapping subtrees means moving whole index ranges, which turns an O(1) pointer swap into O(subtree size).

Four approaches, from naive to production

1 · beginner

Recursion that builds a mirrored copy

time O(n)space O(n) new nodes + O(h) stack

Recursively invert both subtrees, then construct a new node with the results in swapped order.

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    return new TreeNode(root->val, right, left);
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    return new TreeNode(root.val, right, left);
}

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

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

Flaws & bottlenecks

Allocates n new nodes: heap churn and GC pressure that an in-place swap avoids.
Recursion depth equals tree height: a skewed tree of 10⁵ nodes can overflow the call stack.
Callers holding the old root now see a different (unmodified) tree, a hidden semantic difference from "invert in place".

Interviewer cross-questions

Do we need to allocate new nodes?

Say: No. A node's identity does not matter, only its child links. Swapping left and right in place gives the same shape with zero allocation, which is the next approach.

When would the copying version be preferable?

Say: When the original must stay immutable: a persistent or shared tree, or concurrent readers. Copying gives you a new version without locks. With structural sharing you would only copy the spine, not the leaves.

What is the space complexity, precisely?

Say: O(n) for the new tree plus O(h) call stack. If you only count auxiliary space beyond the output, it is O(h).

2 · intermediate

Iterative BFS with a queue

time O(n)space O(w), up to ~n/2

Process nodes level by level: dequeue a node, swap its children, enqueue the (new) children.

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        swap(node->left, node->right);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return root;
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode tmp = node.left; node.left = node.right; node.right = tmp;
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return root;
}

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None: return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return root

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

Flaws & bottlenecks

Queue can hold a whole level: ~n/2 nodes for a perfect tree, which is worse than DFS's O(log n).
Array.shift() is O(n) in many engines, which can make this O(n²); it needs an index pointer or a real deque.
No stack-overflow risk, but extra memory proportional to the widest level.

Interviewer cross-questions

Why use BFS at all if DFS is simpler?

Say: BFS avoids recursion depth limits and naturally gives level order, which helps if I must process levels (e.g., stop at depth k). For plain inversion its memory profile is worse on wide trees.

Does the order of swap vs enqueue matter?

Say: No. Swapping first or enqueuing the original children first both visit every node once; I enqueue after the swap just so the queue order mirrors the new tree.

How do you make dequeue O(1) in JavaScript?

Say: Keep the array and a head index (read queue[head++]) and optionally compact when head exceeds half the length, or implement a ring buffer. Avoid shift() on large arrays.

3 · advanced

Recursive DFS, swap in place

time O(n)space O(h) call stack

At each node swap the two children, then recurse into both. This is the canonical interview answer.

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

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

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

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

Flaws & bottlenecks

Stack depth = height; a degenerate (linked-list-shaped) tree of 10⁵ nodes can throw RangeError: Maximum call stack size exceeded.
Each frame costs return address plus locals: more memory per level than an explicit stack of pointers.
Mutates the input; callers needing the original must copy first.

Interviewer cross-questions

What is the time and space complexity?

Say: Time is Θ(n): each node is visited once with an O(1) swap. Space is O(h) for the call stack: O(log n) if balanced, O(n) if skewed.

Does it matter if we swap before or after recursing?

Say: No. Pre-order (swap, then recurse) and post-order (recurse, then swap) both produce the same tree, because the swap at a node only touches its own pointers. In-order is the exception to be careful with: after swapping, "left" refers to the old right subtree, so you could process one subtree twice and skip the other.

How would you parallelize it?

Say: The two subtrees are independent, so fork one subtree to another task (fork/join) below a depth threshold or a size cutoff to avoid overhead. There is no shared mutable state except each node's own pointers, so no locks are needed.

4 · expert

Iterative DFS with an explicit stack

time O(n)space O(h) heap

Same in-place swap, but drive the traversal with a heap-allocated stack so recursion depth is no longer a limit.

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    vector<TreeNode*> stack{root};
    while (!stack.empty()) {
        TreeNode* node = stack.back(); stack.pop_back();
        TreeNode* left = node->left;
        node->left = node->right;
        node->right = left;
        if (node->left != nullptr) stack.push_back(node->left);
        if (node->right != nullptr) stack.push_back(node->right);
    }
    return root;
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode left = node.left;
        node.left = node.right;
        node.right = left;
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return root;
}

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None: return None
    stack = [root]
    while stack:
        node = stack.pop()
        left = node.left
        node.left = node.right
        node.right = left
        if node.left is not None: stack.append(node.left)
        if node.right is not None: stack.append(node.right)
    return root

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  const stack: TreeNode[] = [root];
  while (stack.length > 0) {
    const node = stack.pop()!;
    const left = node.left;
    node.left = node.right;
    node.right = left;
    if (node.left !== null) stack.push(node.left);
    if (node.right !== null) stack.push(node.right);
  }
  return root;
}

Flaws & bottlenecks

More code and more room for bugs than the recursive version (e.g. forgetting to push both children).
Still O(h) memory, and O(n) for a skewed tree (the stack just lives on the heap).
Not safe against concurrent modification, and mutates the input in place.

Interviewer cross-questions

Why prefer this over recursion in production?

Say: Recursion depth is bounded by the runtime's stack size, typically ~10⁴ frames in V8, so adversarial or degenerate input can crash the process. A heap-allocated stack is limited only by memory and fails gracefully.

Can you do it in O(1) extra space?

Say: Yes, with a Morris-style threaded traversal that temporarily rewires pointers, but it is considerably more complex and mutates links mid-traversal. It rarely justifies itself outside memory-constrained systems.

What edge cases do you test?

Say: null root, single node, a skewed left tree, a skewed right tree, a perfect tree, and a very deep tree (10⁵ nodes) to prove there is no stack overflow. Plus a test that inverting twice returns the original shape.

Synchronized code walkthrough

Showing: Recursion that builds a mirrored copy — shares the player above; click any step to jump.

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);
    return new TreeNode(root->val, right, left);
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);
    return new TreeNode(root.val, right, left);
}

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

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

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        swap(node->left, node->right);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return root;
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode tmp = node.left; node.left = node.right; node.right = tmp;
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return root;
}

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None: return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return root

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

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

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

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

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

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) return nullptr;
    vector<TreeNode*> stack{root};
    while (!stack.empty()) {
        TreeNode* node = stack.back(); stack.pop_back();
        TreeNode* left = node->left;
        node->left = node->right;
        node->right = left;
        if (node->left != nullptr) stack.push_back(node->left);
        if (node->right != nullptr) stack.push_back(node->right);
    }
    return root;
}

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        TreeNode left = node.left;
        node.left = node.right;
        node.right = left;
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return root;
}

def invert_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None: return None
    stack = [root]
    while stack:
        node = stack.pop()
        left = node.left
        node.left = node.right
        node.right = left
        if node.left is not None: stack.append(node.left)
        if node.right is not None: stack.append(node.right)
    return root

function invertTree(root: TreeNode | null): TreeNode | null {
  if (root === null) return null;
  const stack: TreeNode[] = [root];
  while (stack.length > 0) {
    const node = stack.pop()!;
    const left = node.left;
    node.left = node.right;
    node.right = left;
    if (node.left !== null) stack.push(node.left);
    if (node.right !== null) stack.push(node.right);
  }
  return root;
}