Mirror a Binary Tree in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean to mirror a binary tree?

Mirroring a binary tree means swapping the left and right children of every node in the tree, creating a reversed version of the original tree.

beginner

In the mirror operation, what happens to the left and right subtrees of a node?

The left subtree becomes the right subtree, and the right subtree becomes the left subtree after mirroring.

beginner

Show the TypeScript function signature to mirror a binary tree node.

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

beginner

What is the base case in the recursive mirror function for a binary tree?

The base case is when the current node is null, meaning there is no subtree to mirror, so the function returns null.

intermediate

Why is recursion a good approach to mirror a binary tree?

Because each node's left and right subtrees can be mirrored independently, recursion naturally handles this by applying the same operation to smaller parts until the whole tree is mirrored.

What is the first step when mirroring a binary tree node?

A Swap the left and right children of the node

B Delete the node

C Add a new child node

D Do nothing

Mirroring starts by swapping the left and right children of the current node.

What should the mirror function return when it receives a null node?

A null

B a new node

C the original node

D an error

When the node is null, the function returns null as there is nothing to mirror.

Which traversal method is naturally used in the mirror function?

A Level order traversal

B Inorder traversal

C Preorder traversal

D Postorder traversal

Preorder traversal is used because we swap children before recursively mirroring subtrees.

After mirroring, what happens to the original left subtree?

A It is deleted

B It becomes the right subtree

C It stays as the left subtree

D It becomes the root

The original left subtree becomes the right subtree after mirroring.

What is the time complexity of mirroring a binary tree with n nodes?

A O(log n)

B O(1)

C O(n^2)

D O(n)

Each node is visited once, so the time complexity is O(n).

Explain how you would mirror a binary tree using recursion.

Think about what happens at each node and how recursion helps.

Describe the changes in the tree structure after mirroring a binary tree.

Imagine flipping the tree like a mirror image.

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