Mirror a Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Swap left and right children

↓

Recursively mirror left subtree

↓

Recursively mirror right subtree

↓

Return mirrored subtree

↓

Done when all nodes processed

Start from the root, swap its left and right children, then do the same for each subtree recursively until all nodes are mirrored.

Execution Sample

DSA Typescript

function mirror(node: TreeNode | null): TreeNode | null {
  if (!node) return null;
  [node.left, node.right] = [mirror(node.right), mirror(node.left)];
  return node;
}

This function swaps left and right children of each node recursively to mirror the binary tree.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State (Visual)
1	Start at root	1	None	1 / \ 2 3 / \ \ 4 5 6
2	Swap children of node 1	1	left <-> right swapped	1 / \ 3 2 / / \ 6 4 5
3	Mirror left subtree of node 1 (node 3)	3	None yet	1 / \ 3 2 / / \ 6 4 5
4	Swap children of node 3	3	left <-> right swapped	1 / \ 3 2 \ / \ 6 4 5
5	Mirror left subtree of node 3 (null)	null	None	1 / \ 3 2 \ / \ 6 4 5
6	Mirror right subtree of node 3 (node 6)	6	None	1 / \ 3 2 \ / \ 6 4 5
7	Swap children of node 6	6	left <-> right swapped (both null)	1 / \ 3 2 \ / \ 6 4 5
8	Mirror left subtree of node 6 (null)	null	None	1 / \ 3 2 \ / \ 6 4 5
9	Mirror right subtree of node 6 (null)	null	None	1 / \ 3 2 \ / \ 6 4 5
10	Mirror right subtree of node 1 (node 2)	2	None yet	1 / \ 3 2 \ / \ 6 4 5
11	Swap children of node 2	2	left <-> right swapped	1 / \ 3 2 \ / \ 6 5 4
12	Mirror left subtree of node 2 (node 5)	5	None	1 / \ 3 2 \ / \ 6 5 4
13	Swap children of node 5	5	left <-> right swapped (both null)	1 / \ 3 2 \ / \ 6 5 4
14	Mirror left subtree of node 5 (null)	null	None	1 / \ 3 2 \ / \ 6 5 4
15	Mirror right subtree of node 5 (null)	null	None	1 / \ 3 2 \ / \ 6 5 4
16	Mirror right subtree of node 2 (node 4)	4	None	1 / \ 3 2 \ / \ 6 5 4
17	Swap children of node 4	4	left <-> right swapped (both null)	1 / \ 3 2 \ / \ 6 5 4
18	Mirror left subtree of node 4 (null)	null	None	1 / \ 3 2 \ / \ 6 5 4
19	Mirror right subtree of node 4 (null)	null	None	1 / \ 3 2 \ / \ 6 5 4
20	All nodes processed, return mirrored tree	null	None	1 / \ 3 2 \ / \ 6 5 4

💡 All nodes visited and their children swapped, recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 11	After Step 17	Final
node	1 (root)	1	3 (left child of root)	6 (left child of 3)	2 (right child of root)	4 (right child of 2)	null (end)
left child	2	3	null	null	5	null	null
right child	3	2	6	null	4	null	null

Key Moments - 3 Insights

Why do we swap children before recursively calling mirror on subtrees?

Swapping first ensures that when recursion goes down, it mirrors the correct new left and right subtrees. See execution_table steps 2 and 4 where swap happens before recursive calls.

What happens when a node is null?

The function returns immediately without changes, as shown in steps 5, 8, 9, 14, 15, 18, 19 where null nodes cause no action.

Why does the tree structure change visually after each swap?

Because swapping left and right pointers changes the physical layout of the tree, as seen in the Tree State column after steps 2, 4, and 11.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what change happens to node 1?

A Its left and right children are swapped

B Its children are set to null

C It is deleted

D No change

💡 Hint

Check the Pointer Changes and Tree State columns at step 2.

At which step does the function process node 6?

A Step 4

B Step 6

C Step 11

D Step 17

💡 Hint

Look for 'Node Visited' column in execution_table.

If we skip swapping children at each node, how would the final tree state differ?

A The tree would be fully mirrored

B The tree would be empty

C The tree would remain unchanged

D Only leaf nodes would swap

💡 Hint

Refer to the concept_flow and execution_table steps where swapping is key.

Concept Snapshot

Mirror a Binary Tree:
- Swap left and right children of each node
- Do this recursively for all nodes
- Base case: if node is null, return
- Result: tree structure flipped horizontally
- Use recursion to handle all subtrees

Full Transcript

To mirror a binary tree, start at the root node. Swap its left and right children pointers. Then recursively do the same for the left subtree and the right subtree. If a node is null, return immediately. This process flips the tree horizontally. The code swaps children first, then calls mirror recursively on the swapped children. The recursion ends when all nodes have been processed. The tree's visual structure changes after each swap, showing the mirror effect.