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.

Practice

1. What does it mean to mirror a binary tree?

easy

A. Swap the left and right children of every node in the tree

B. Remove all leaf nodes from the tree

C. Convert the tree into a linked list

D. Sort the tree nodes in ascending order

Solution

1. Step 1: Understand the mirror operation

   Mirroring a binary tree means swapping the left and right children of every node.

2. Step 2: Effect on the tree structure

   This operation flips the tree around its center, creating a mirror image.

3. Final Answer:

   Swap the left and right children of every node in the tree -> Option A

4. Quick Check:

   Mirror = Swap children [OK]

Hint: Mirror means swapping left and right children at all nodes [OK]

Common Mistakes:

• Thinking mirror means sorting nodes
• Confusing mirror with removing nodes
• Assuming mirror changes node values

2. Which of the following TypeScript function signatures correctly represents a function to mirror a binary tree node?

easy

A. function mirrorTree(root: string): string

B. function mirrorTree(root: number): number

C. function mirrorTree(root: TreeNode): void

D. function mirrorTree(root: TreeNode | null): TreeNode | null

Solution

1. Step 1: Identify the input and output types

   The function should accept a TreeNode or null and return a TreeNode or null after mirroring.

2. Step 2: Check each option's signature

   function mirrorTree(root: TreeNode | null): TreeNode | null matches the expected input and output types for a binary tree mirror function.

3. Final Answer:

   function mirrorTree(root: TreeNode | null): TreeNode | null -> Option D

4. Quick Check:

   Correct signature uses TreeNode or null [OK]

Hint: Mirror function inputs and outputs TreeNode or null [OK]

Common Mistakes:

• Using primitive types like number or string instead of TreeNode
• Returning void instead of the mirrored tree
• Not allowing null as input

3. Given the following TypeScript code, what is the output when the tree is mirrored and then printed in preorder?

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

function mirrorTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  const left = mirrorTree(root.left);
  const right = mirrorTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

function preorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
const mirrored = mirrorTree(tree);
console.log(preorder(mirrored));

medium

A. [1, 2, 4, 5, 3]

B. [1, 3, 2, 5, 4]

C. [1, 3, 5, 4, 2]

D. [1, 2, 5, 4, 3]

Solution

1. Step 1: Understand the original tree structure

   The tree is:
   1
   ├─ 2
   │ ├─ 4
   │ └─ 5
   └─ 3

2. Step 2: Mirror the tree by swapping left and right children

   After mirroring:
   1
   ├─ 3
   └─ 2
   ├─ 5
   └─ 4

3. Step 3: Preorder traversal of mirrored tree

   Preorder visits root, left, right:
   1, 3, 2, 5, 4

4. Final Answer:

   [1, 3, 2, 5, 4] -> Option B

5. Quick Check:

   Mirror preorder = [1, 3, 2, 5, 4] [OK]

Hint: Mirror swaps children; preorder visits root-left-right [OK]

Common Mistakes:

• Not swapping children correctly
• Confusing preorder with inorder or postorder
• Forgetting to mirror recursively

4. The following TypeScript function is intended to mirror a binary tree but contains a bug. What is the bug?

function mirrorTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  mirrorTree(root.left);
  mirrorTree(root.right);
  const temp = root.left;
  root.left = root.right;
  root.right = temp;
  return root;
}

medium

A. The base case should return root instead of null

B. The swapping of left and right children is done before recursion

C. The recursive calls do not assign the mirrored subtrees back to root.left and root.right

D. The function does not handle empty trees

Solution

1. Step 1: Analyze the recursive calls

   The function calls mirrorTree on root.left and root.right but does not assign the results back to root.left and root.right.

2. Step 2: Understand the effect of missing assignments

   Without assigning, the subtrees are not updated with their mirrored versions, so the mirror is incomplete.

3. Final Answer:

   The recursive calls do not assign the mirrored subtrees back to root.left and root.right -> Option C

4. Quick Check:

   Assign recursive results to children [OK]

Hint: Always assign recursive mirror results back to children [OK]

Common Mistakes:

• Ignoring return values of recursive calls
• Swapping children before recursion
• Incorrect base case handling

5. You have a binary tree where some nodes have only one child (either left or right). After mirroring the tree using the standard mirror function, which of the following statements is true about the structure of the mirrored tree?

hard

A. Nodes with only left child will have only right child after mirroring

B. Nodes with only left child will have no children after mirroring

C. Nodes with only right child will have both children after mirroring

D. The tree structure remains unchanged after mirroring

Solution

1. Step 1: Understand mirroring effect on single-child nodes

   Mirroring swaps left and right children of every node.

2. Step 2: Effect on nodes with only one child

   If a node has only a left child, after mirroring, that child becomes the right child, and left becomes null.

3. Final Answer:

   Nodes with only left child will have only right child after mirroring -> Option A

4. Quick Check:

   Mirror swaps children, single left child becomes right [OK]

Hint: Mirror swaps children, single left child moves to right [OK]

Common Mistakes:

• Assuming children disappear after mirroring
• Thinking mirroring adds children
• Believing tree structure stays same