Mirror a Binary Tree in DSA Javascript

Mental Model

Flipping a binary tree means swapping every left child with its right child, all the way down the tree.

Analogy: Imagine holding a tree-shaped mirror and seeing the tree's left and right sides swapped exactly like a reflection.

    1
   / \
  2   3
 / \ / \
4  5 6  7

(Each node points to left and right children)

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5; 3 has children 6 and 7

Goal: Transform the tree so that left and right children of every node are swapped, producing a mirror image

Step 1: Start at root node 1, swap its left and right children

    1
   / \
  3   2
 / \ / \
6  7 4  5

Why: Swapping children at root begins the mirroring process

Step 2: Move to left child (3), swap its children 6 and 7

    1
   / \
  3   2
 / \ / \
7  6 4  5

Why: Swapping children of node 3 mirrors its subtree

Step 3: Move to right child (2), swap its children 4 and 5

    1
   / \
  3   2
 / \ / \
7  6 5  4

Why: Swapping children of node 2 completes mirroring of the tree

Result:

    1
   / \
  3   2
 / \ / \
7  6 5  4

Annotated Code

DSA Javascript

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

function mirrorTree(root) {
  if (root === null) return null; // base case: empty node

  // swap left and right children
  const temp = root.left;
  root.left = root.right;
  root.right = temp;

  // recursively mirror left subtree
  mirrorTree(root.left);
  // recursively mirror right subtree
  mirrorTree(root.right);

  return root;
}

// Driver code to build tree and test
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, new TreeNode(6), new TreeNode(7))
);

mirrorTree(root);

function printTree(node) {
  if (!node) return "null";
  const left = printTree(node.left);
  const right = printTree(node.right);
  return `${node.val} -> (${left}, ${right})`;
}

console.log(printTree(root));

if (root === null) return null; // base case: empty node

stop recursion when node is empty

const temp = root.left; root.left = root.right; root.right = temp;

swap left and right children of current node

mirrorTree(root.left);

recursively mirror left subtree (which was originally right subtree)

mirrorTree(root.right);

recursively mirror right subtree (which was originally left subtree)

Output

1 -> (3 -> (7 -> (null, null), 6 -> (null, null)), 2 -> (5 -> (null, null), 4 -> (null, null)))

Complexity Analysis

Time: O(n) because we visit each node exactly once to swap children

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: Iterative approaches exist but recursion is simpler and intuitive; iterative may use explicit stack with similar time and space

Edge Cases

Empty tree (root is null)

Function returns null immediately without error

DSA Javascript

if (root === null) return null; // base case: empty node

Tree with single node (no children)

Swapping children does nothing, returns the same single node

DSA Javascript

const temp = root.left;
root.left = root.right;
root.right = temp;

Tree with only left or only right children

Children are swapped correctly, turning left-only subtree into right-only and vice versa

DSA Javascript

const temp = root.left;
root.left = root.right;
root.right = temp;

When to Use This Pattern

When asked to flip or invert a binary tree structure, use the mirror tree pattern by swapping left and right children recursively.

Common Mistakes

Mistake: Swapping children but forgetting to recursively mirror subtrees
Fix: Add recursive calls to mirrorTree on both left and right children after swapping

Mistake: Swapping children incorrectly by assigning without a temporary variable
Fix: Use a temporary variable to hold one child before swapping to avoid losing reference

Summary

It flips a binary tree by swapping every node's left and right children.

Use it when you need the mirror image of a binary tree.

The key is to swap children at each node and do this recursively down the tree.