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.

Practice

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

easy

A. Sort the nodes in ascending order

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

C. Convert the tree into a linked list

D. Remove all leaf nodes from the tree

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: Apply the definition to the tree

   By swapping children at every node, the tree becomes a mirror image of the original.

3. Final Answer:

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

4. Quick Check:

   Mirror = Swap children [OK]

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

Common Mistakes:

• Thinking mirror means deleting nodes
• Confusing mirror with sorting
• Assuming mirror flattens the tree

2. Which of the following is the correct JavaScript syntax to swap the left and right children of a node named node?

easy

A. let temp = node.left; node.left = node.right; node.right = temp;

B. node.left = node.right; node.right = node.left;

C. node.left, node.right = node.right, node.left;

D. swap(node.left, node.right);

Solution

1. Step 1: Understand swapping variables in JavaScript

   To swap two variables, use a temporary variable to hold one value during the swap.

2. Step 2: Check each option

   let temp = node.left; node.left = node.right; node.right = temp; correctly uses a temporary variable to swap node.left and node.right. node.left = node.right; node.right = node.left; overwrites node.left before assigning node.right. node.left, node.right = node.right, node.left; uses invalid syntax in JavaScript. swap(node.left, node.right); calls an undefined function.

3. Final Answer:

   let temp = node.left; node.left = node.right; node.right = temp; -> Option A

4. Quick Check:

   Use temp variable to swap [OK]

Hint: Use a temp variable to swap two values in JavaScript [OK]

Common Mistakes:

• Overwriting one child before saving it
• Using Python-style tuple swap syntax
• Calling undefined swap functions

3. What is the output of the following code that mirrors a binary tree?

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function mirror(node) {
  if (!node) return null;
  let left = mirror(node.left);
  let right = mirror(node.right);
  node.left = right;
  node.right = left;
  return node;
}

// Tree before mirroring:
//     1
//    / \
//   2   3
//  /     \
// 4       5

let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.right = new Node(5);

mirror(root);

function printTree(node) {
  if (!node) return 'null';
  return node.val + ' -> ' + printTree(node.left) + ', ' + printTree(node.right);
}

console.log(printTree(root));

medium

A. 1 -> 2 -> 4 -> null, 3 -> 5 -> null, null

B. 1 -> 3 -> 4 -> null, 2 -> 5 -> null, null

C. 1 -> 3 -> null, 2 -> 5 -> null, 4

D. 1 -> 3 -> 5 -> null, 2 -> 4 -> null, null

Solution

1. Step 1: Understand the mirror function

   The mirror function swaps left and right children recursively for every node.

2. Step 2: Trace the tree after mirroring

   Original tree: 1 with left=2 and right=3; 2 has left=4; 3 has right=5.
   After mirroring:
   1's left becomes 3, right becomes 2.
   3's left becomes 5, right becomes null.
   2's left becomes null, right becomes 4.
   Printing in preorder with left then right shows: 1 -> 3 -> 5 -> null, 2 -> 4 -> null, null.

3. Final Answer:

   1 -> 3 -> 5 -> null, 2 -> 4 -> null, null -> Option D

4. Quick Check:

   Mirror swaps children recursively [OK]

Hint: Trace swaps at each node recursively [OK]

Common Mistakes:

• Not swapping children at all nodes
• Mixing left and right children incorrectly
• Misreading the print output format

4. Find the error in the following mirror function and select the correct fix:

function mirror(node) {
  if (node == null) return;
  mirror(node.left);
  mirror(node.right);
  let temp = node.left;
  node.left = node.right;
  node.right = temp;
}

medium

A. The function should return the node after swapping children

B. The base case should check for undefined instead of null

C. The swap should happen before recursive calls

D. The temp variable should be declared outside the function

Solution

1. Step 1: Analyze the function behavior

   The function swaps children after recursive calls but does not return the node, so the caller gets undefined.

2. Step 2: Identify the fix

   Returning the node after swapping ensures the mirrored subtree is returned properly for further use.

3. Final Answer:

   The function should return the node after swapping children -> Option A

4. Quick Check:

   Return node after swap [OK]

Hint: Always return the node after modifying it in recursion [OK]

Common Mistakes:

• Not returning the node causes undefined results
• Swapping before recursion breaks logic
• Misunderstanding null vs undefined checks

5. Given a binary tree where some nodes have only one child, how does the mirror function handle these nodes?
Consider the tree:

    10
   /  
  20   
    \
     30

What will be the structure after mirroring?

hard

A. 10 with left child 30 and right child 20; 20 and 30 have no children

B. 10 with left child 20 and right null; 20 with left null and right 30

C. 10 with left child null and right child 20; 20 with left child 30 and right null

D. 10 with left child null and right child 30; 30 with left child 20 and right null

Solution

1. Step 1: Understand mirroring nodes with single children

   Mirroring swaps left and right children even if one child is null.

2. Step 2: Apply mirror to given tree

   Original:
   10 has left=20, right=null
   20 has left=null, right=30
   After mirror:
   10's left becomes null, right becomes 20
   20's left becomes 30, right becomes null

3. Final Answer:

   10 with left child null and right child 20; 20 with left child 30 and right null -> Option C

4. Quick Check:

   Mirror swaps children even if one is null [OK]

Hint: Swap children even if one child is missing [OK]

Common Mistakes:

• Ignoring null children during swap
• Assuming children move to wrong side
• Confusing node values with positions