Mirror a Binary Tree in DSA Typescript

Mental Model

Flipping a binary tree means swapping every left child with its right child, like looking at the tree in a mirror.

Analogy: Imagine holding a tree-shaped paper cutout in front of a mirror; the left side becomes the right side and vice versa.

    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, creating 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 flips the top level

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

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

Why: Swapping children at node 3 flips its subtree

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

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

Why: Swapping children at node 2 flips its subtree

Step 4: Leaf nodes 7, 6, 5, 4 have no children, so no swaps needed

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

Why: Leaves are base case, no children to swap

Result:

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

Annotated Code

DSA Typescript

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

function mirrorTree(root: TreeNode | null): TreeNode | null {
  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: TreeNode | null): string {
  if (node === null) return "null";
  const leftStr = printTree(node.left);
  const rightStr = printTree(node.right);
  return `${node.val} -> (${leftStr}, ${rightStr})`;
}

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 each node is visited once to swap children

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

vs Alternative: Iterative approach with a stack can also be used but recursion is simpler and intuitive here

Edge Cases

Empty tree (root is null)

Function returns null immediately without error

DSA Typescript

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

Tree with single node

No swaps happen, function returns the same single node

DSA Typescript

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

Tree with only left or only right children

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

DSA Typescript

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

When to Use This Pattern

When you need to flip or reverse the structure of a binary tree, think of the mirror tree pattern because it swaps children recursively to create a mirrored shape.

Common Mistakes

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

Mistake: Swapping children incorrectly by overwriting without a temporary variable
Fix: Use a temporary variable to hold one child before swapping

Summary

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

Use it when you want to create a mirror image of a binary tree.

The key is to swap children at each node and then do the same for their subtrees recursively.