Mirror a Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Mirroring a Simple Binary Tree

What is the output of the following TypeScript code that mirrors a binary tree and prints its inorder traversal?

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) return null;
  const left = mirrorTree(root.left);
  const right = mirrorTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

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

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
mirrorTree(root);
console.log(inorder(root));

A [3, 1, 2]

B [2, 1, 3]

C [1, 2, 3]

D [3, 2, 1]

💡 Hint

Think about how inorder traversal visits nodes after mirroring the left and right children.

The mirrorTree function swaps the left and right children recursively. The original tree is:

1
/ \
2 3

After mirroring, it becomes:

1
/ \
3 2

Inorder traversal visits left, root, right, so the output is [3, 1, 2].

🧠 Conceptual

intermediate

Understanding Mirror Tree Recursive Calls

In the mirrorTree function, what is the main purpose of the recursive calls before swapping the children?

A To swap the left and right children of the current node only

B To print the values of the nodes in preorder

C To count the number of nodes in the tree

D To ensure the entire left and right subtrees are mirrored before swapping

💡 Hint

Think about what happens if you swap children before mirroring subtrees.

The recursive calls mirror the left and right subtrees fully before swapping them at the current node. This ensures the entire tree is mirrored correctly.

🔧 Debug

advanced

Identify the Bug in Mirror Tree Implementation

What error will this code produce when trying to mirror a binary tree?

DSA Typescript

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;
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
mirrorTree(root);
console.log(root.left?.val);

A No error; output is 3

B TypeError because root.left or root.right is undefined

C Stack overflow due to infinite recursion

D Output is 2 instead of 3

💡 Hint

Check if the recursive calls are used correctly and if swapping is done properly.

The code correctly mirrors the tree by recursively calling mirrorTree on left and right subtrees, then swapping them. The output root.left?.val is 3 after mirroring.

❓ Predict Output

advanced

Output of Mirroring a Larger Binary Tree

What is the output of the inorder traversal after mirroring this binary tree?

DSA Typescript

const root = new TreeNode(4,
  new TreeNode(2, new TreeNode(1), new TreeNode(3)),
  new TreeNode(7, new TreeNode(6), new TreeNode(9))
);
mirrorTree(root);
console.log(inorder(root));

A [1, 2, 3, 4, 6, 7, 9]

B [9, 7, 6, 4, 3, 2, 1]

C [6, 7, 9, 4, 1, 2, 3]

D [3, 2, 1, 4, 9, 7, 6]

💡 Hint

Remember mirroring swaps left and right subtrees at every node.

The original inorder traversal is [1, 2, 3, 4, 6, 7, 9]. After mirroring, the tree's left and right children are swapped at every node, reversing the inorder traversal to [9, 7, 6, 4, 3, 2, 1].

🧠 Conceptual

expert

Time Complexity of Mirroring a Binary Tree

What is the time complexity of the mirrorTree function for a binary tree with n nodes?

A O(log n), because the tree is divided in half each recursion

B O(n^2), because each node swaps children multiple times

C O(n), because each node is visited once

D O(1), because swapping is done in constant time

💡 Hint

Consider how many times the function visits each node.

The mirrorTree function visits each node exactly once to swap its children, so the time complexity is O(n).