Skip to content
Shubham JangleResources
Trees

Explore topics

Invert Binary Tree

Watch the walkthrough
Open on Instagram

Problem

Swap the left and right children at every node and return the root. This mutates the tree.

Approach and revision checks

Recursive traversal uses O(h) stack; breadth-first traversal needs O(w) queue space with an efficient queue. Both visit each node once. The copied _invertTree calls invertTree (the iterative version) for its subtrees rather than calling itself, so it is a mixed implementation. The iterative version also uses shift; account for that queue cost. Inverting twice should restore the original structure.

Original repository source

Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.

9-invert-binary-tree.js

Original file on GitHub

// TC: O(N) SC: O(1) Stack Space: O(N)
var _invertTree = function (root) {
  if (!root) return null;

  let left = invertTree(root.left);
  let right = invertTree(root.right);

  root.left = right;
  root.right = left;

  return root;
};

// TC: O(N) SC: O(N)
var invertTree = function (root) {
  if (!root) return null;
  const q = [root]; // queue

  while (q.length) {
    const curr = q.shift();

    const temp = curr.left;
    curr.left = curr.right;
    curr.right = temp;

    if (curr.left) q.push(curr.left);
    if (curr.right) q.push(curr.right);
  }

  return root;
};