Invert Binary Tree
Watch the walkthrough
Open on InstagramProblem
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
// 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;
};