Mirror a Binary Tree in DSA Javascript - Deep Dive

Overview - Mirror a Binary Tree

What is it?

Mirroring a binary tree means creating a new tree where the left and right children of every node are swapped. Imagine flipping the tree as if looking at it in a mirror. This changes the structure but keeps the same values, just reversed in position. It helps us understand tree transformations and symmetry.

Why it matters

Without the ability to mirror a tree, we would miss out on understanding how tree structures can be transformed and manipulated. This operation is useful in problems involving symmetry, image processing, and reversing hierarchical data. It also helps in learning how to traverse and modify trees efficiently.

Where it fits

Before learning to mirror a binary tree, you should understand what a binary tree is and how to traverse it (like preorder, inorder, and postorder). After mastering mirroring, you can explore tree rotations, balancing trees, and advanced tree algorithms like AVL or Red-Black trees.

Mental Model

Core Idea

Mirroring a binary tree means swapping every node's left and right children recursively to create a reversed structure.

Think of it like...

It's like looking at a family tree photo in a mirror: every branch on the left appears on the right and vice versa, but the people (nodes) stay the same.

Original Tree:          Mirrored Tree:
    1                         1
   / \                       / \
  2   3                     3   2
 / \   \                   /   / \
4   5   6                 6   5   4

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. Each node holds a value and pointers to its children or null if none. For example, a node with value 1 might have left child 2 and right child 3.

Result

You can visualize and represent a binary tree with nodes and their left/right links.

Understanding the basic structure of a binary tree is essential before changing or manipulating it.

2

Foundation

Traversing a Binary Tree

Concept: Learn how to visit each node in a tree using preorder traversal.

Preorder traversal visits the current node first, then recursively visits the left child, then the right child. For example, for tree with root 1, left 2, right 3, preorder visits nodes in order: 1, 2, 3.

Result

You can list all nodes in a specific order, which helps in processing or modifying the tree.

Traversal is the foundation for any tree operation, including mirroring.

3

Intermediate

Swapping Left and Right Children

🤔Before reading on: do you think swapping children at each node changes the node values or just their positions? Commit to your answer.

Concept: Mirroring involves swapping the left and right children pointers of each node without changing the node values.

At each node, we swap the left child pointer with the right child pointer. This means if a node had left child 2 and right child 3, after swapping, left child becomes 3 and right child becomes 2.

Result

The tree structure is reversed horizontally, but node values remain the same.

Knowing that only pointers swap, not values, helps avoid confusion and errors in implementation.

4

Intermediate

Recursive Mirroring Algorithm

🤔Before reading on: do you think mirroring a tree can be done without recursion? Commit to your answer.

Concept: Use recursion to mirror the tree by swapping children at each node and recursively mirroring subtrees.

Algorithm steps: 1. If node is null, return. 2. Swap left and right children. 3. Recursively mirror left subtree. 4. Recursively mirror right subtree. This ensures every node's children are swapped down the tree.

Result

The entire tree is mirrored correctly after recursion completes.

Recursion naturally fits tree problems because trees are recursive structures.

5

Advanced

Iterative Mirroring Using a Stack

🤔Before reading on: do you think recursion is the only way to mirror a tree? Commit to your answer.

Concept: Mirroring can also be done iteratively using a stack to avoid recursion.

Algorithm steps: 1. Initialize a stack and push the root node. 2. While stack not empty: a. Pop a node. b. Swap its children. c. Push non-null children to stack. This simulates recursion using a stack.

Result

The tree is mirrored without using recursion, useful for deep trees to avoid stack overflow.

Understanding iterative methods helps handle large trees and environments where recursion is limited.

6

Expert

In-Place Mirroring and Memory Efficiency

🤔Before reading on: do you think mirroring requires creating a new tree or can be done in-place? Commit to your answer.

Concept: Mirroring can be done in-place by swapping children pointers without creating new nodes, saving memory.

The algorithm swaps children pointers directly on the existing tree nodes. No new nodes are created. This is efficient in time and space, but modifies the original tree permanently.

Result

The original tree is transformed into its mirror image without extra memory allocation.

Knowing in-place operations saves resources and is critical in memory-constrained environments.

Under the Hood

Mirroring works by recursively or iteratively visiting each node and swapping its left and right child pointers. Internally, this changes the references in memory so that the left subtree becomes the right subtree and vice versa. The recursion stack or explicit stack keeps track of nodes to process. No new nodes are created; only pointers are changed.

Why designed this way?

This approach leverages the recursive nature of trees, making the code simple and elegant. Alternatives like creating a new mirrored tree would use more memory and be slower. Swapping pointers in-place is efficient and aligns with how trees are stored in memory as linked nodes.

┌─────────────┐       ┌─────────────┐
│   Node 1    │       │   Node 1    │
│  /       \  │       │  /       \  │
│ N2       N3 │  -->  │ N3       N2 │
└─────────────┘       └─────────────┘
     /  \                 /  \
   N4    N5             N6    N5

Myth Busters - 4 Common Misconceptions

Quick: Does mirroring a binary tree change the values inside the nodes? Commit to yes or no.

Common Belief: Mirroring changes the values of the nodes to reflect the new structure.

Reality: Mirroring only swaps the positions (left and right children) of nodes; the values inside nodes remain unchanged.

Why it matters: If you mistakenly change values, you corrupt the data and lose the original information.

Quick: Can mirroring be done without visiting every node? Commit to yes or no.

Common Belief: You can mirror a tree by just swapping the root's children once.

Reality: Every node's children must be swapped to fully mirror the tree; skipping nodes leads to incorrect results.

Why it matters: Partial mirroring causes inconsistent tree structure and bugs in algorithms relying on full mirroring.

Quick: Is recursion the only way to mirror a binary tree? Commit to yes or no.

Common Belief: Mirroring requires recursion because trees are recursive structures.

Reality: Mirroring can also be done iteratively using a stack or queue to simulate recursion.

Why it matters: Knowing iterative methods helps avoid stack overflow in deep trees and improves performance.

Quick: Does mirroring a binary tree always produce a balanced tree? Commit to yes or no.

Common Belief: Mirroring a tree balances it by swapping children.

Reality: Mirroring only reverses the structure; it does not balance the tree or affect its height.

Why it matters: Assuming mirroring balances the tree can lead to wrong assumptions about tree performance.

Expert Zone

1

Mirroring a tree in-place modifies the original structure, which may not be desirable if the original tree is needed later.

2

Iterative mirroring can be optimized by using a queue for breadth-first traversal, which mirrors the tree level by level.

3

In functional programming, mirroring often involves creating a new mirrored tree instead of modifying in-place, preserving immutability.

When NOT to use

Avoid in-place mirroring when you need to keep the original tree intact; instead, create a new mirrored copy. Also, for very large trees with limited stack size, prefer iterative methods over recursion to prevent stack overflow.

Production Patterns

Mirroring is used in image processing to flip hierarchical data, in UI frameworks to support right-to-left layouts, and in algorithms that require symmetric tree comparisons or transformations.

Connections

Tree Traversal

Mirroring builds on tree traversal by visiting nodes systematically to swap children.

Understanding traversal methods is essential to implement mirroring correctly and efficiently.

Graph Isomorphism

Mirroring a tree is a special case of graph transformation that preserves node values but changes edge directions.

Knowing graph transformations helps in understanding how tree structures relate to more complex networks.

Symmetry in Art and Design

Mirroring in trees is analogous to symmetry operations in art, where flipping an image creates a balanced reflection.

Recognizing symmetry in different fields deepens appreciation of structural transformations and their applications.

Common Pitfalls

#1 Swapping node values instead of pointers.

Wrong approach:

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

Correct approach:

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

Root cause:

Confusing node values with node pointers leads to incorrect swapping and data corruption.

#2 Not handling null nodes before swapping.

Wrong approach:

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

Correct approach:

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

Root cause:

Failing to check for null causes runtime errors when trying to access properties of null.

#3 Creating a new tree without freeing old nodes in memory-constrained environments.

Wrong approach:

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

Correct approach:

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

Root cause:

Creating new nodes duplicates memory usage and may cause inefficiency or memory overflow.

Key Takeaways

Mirroring a binary tree swaps the left and right children of every node, reversing the tree structure horizontally.

This operation can be done recursively or iteratively, with recursion being the natural fit for tree structures.

Mirroring is done in-place by swapping pointers, not by changing node values or creating new nodes, which saves memory.

Understanding tree traversal is essential to implement mirroring correctly and avoid common mistakes.

Mirroring does not balance a tree; it only reverses its shape, so it should not be confused with tree balancing operations.

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