Mirror a Binary Tree in DSA Rust - Execution Trace

Concept Flow - Mirror a Binary Tree

Start at root node

↓

Swap left and right child

↓

Mirror left subtree

↓

Mirror right subtree

↓

Return mirrored subtree

Start from the root, swap its left and right children, then recursively do the same for each subtree.

Execution Sample

DSA Rust

fn mirror(node: &mut Option<Box<TreeNode>>) {
    if let Some(n) = node {
        let left = n.left.take();
        let right = n.right.take();
        n.left = right;
        n.right = left;
        mirror(&mut n.left);
        mirror(&mut n.right);
    }
}

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=3, right=2	1 / \ 3 2 \ / \ 6 4 5
3	Mirror left subtree of node 1 (node 3)	3	None	1 / \ 3 2 \ / \ 6 4 5
4	Swap children of node 3	3	left=None, right=6	1 / \ 3 2 / / \ None 4 5 \ 6
5	Mirror left subtree of node 3 (None)	None	None	No change
6	Mirror right subtree of node 3 (node 6)	6	None	1 / \ 3 2 / / \ None 4 5 \ 6
7	Swap children of node 6	6	left=None, right=None	1 / \ 3 2 / / \ None 4 5 \ 6
8	Mirror left subtree of node 6 (None)	None	None	No change
9	Mirror right subtree of node 6 (None)	None	None	No change
10	Mirror right subtree of node 1 (node 2)	2	None	1 / \ 3 2 / / \ None 4 5 \ 6
11	Swap children of node 2	2	left=5, right=4	1 / \ 3 2 / / \ None 5 4 \ 6
12	Mirror left subtree of node 2 (node 5)	5	None	1 / \ 3 2 / / \ None 5 4 \ 6
13	Swap children of node 5	5	left=None, right=None	No change
14	Mirror left subtree of node 5 (None)	None	None	No change
15	Mirror right subtree of node 5 (None)	None	None	No change
16	Mirror right subtree of node 2 (node 4)	4	None	1 / \ 3 2 / / \ None 5 4 \ 6
17	Swap children of node 4	4	left=None, right=None	No change
18	Mirror left subtree of node 4 (None)	None	None	No change
19	Mirror right subtree of node 4 (None)	None	None	No change
20	Return from root	1	None	1 / \ 3 2 / / \ None 5 4 \ 6

💡 All nodes visited and children swapped; recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 11	Final
node	root=1	root=1	node=3	node=2	root=1
left child	2	3	None	5	3 or 5 depending on subtree
right child	3	2	6	4	2 or 4 depending on subtree
tree state	Original tree	Root children swapped	Node 3 children swapped	Node 2 children swapped	Fully mirrored tree

Key Moments - 3 Insights

Why do we swap the left and right children before recursively mirroring subtrees?

Swapping first ensures that when we recursively call mirror on the new left and right children, we are mirroring the correct subtrees. This is shown in execution_table steps 2 and 3 where after swapping node 1's children, we mirror the new left subtree (originally right subtree).

What happens when a node has no children (None)?

When a node's child is None, the recursion stops for that path as shown in steps 5, 8, 9, 14, 15, 18, and 19 where mirror is called on None and no changes occur.

Why do we use 'take()' on children before swapping?

Using 'take()' temporarily removes the child nodes so we can swap them without borrowing conflicts. This is implicit in the code and reflected in pointer changes in steps like 2 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what are the new left and right children of node 1?

A Left = 2, Right = 3

B Left = 3, Right = 2

C Left = 4, Right = 5

D Left = None, Right = None

💡 Hint

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

At which step does the mirror function first handle a leaf node with no children?

A Step 4

B Step 13

C Step 7

D Step 17

💡 Hint

Look for the first node where both left and right children are None in execution_table.

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

A The tree would remain unchanged

B Only leaf nodes would be swapped

C The tree would be mirrored correctly anyway

D The tree would become empty

💡 Hint

Refer to the concept_flow and execution_table steps showing swapping is essential before recursive calls.

Concept Snapshot

Mirror a Binary Tree:
- Swap left and right children of each node
- Recursively mirror left and right subtrees
- Base case: node is None (stop)
- Use recursion to traverse entire tree
- Result: tree structure flipped horizontally

Full Transcript

To mirror a binary tree, start at the root node. Swap its left and right children. Then recursively do the same for the left subtree and the right subtree. If a node is None, stop recursion there. This process flips the tree horizontally. The Rust code uses 'take()' to safely swap children. The execution table shows each step: starting at root, swapping children, then moving down to subtrees. Leaf nodes with no children cause recursion to stop. This method ensures the entire tree is mirrored correctly.

Practice

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

easy

A. Swap the left and right children of every node

B. Remove all leaf nodes

C. Convert the tree into a linked list

D. Sort the 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 in the tree.

2. Step 2: Effect on the tree structure

   This operation creates a tree that is a mirror image of the original, flipping it horizontally.

3. Final Answer:

   Swap the left and right children of every node -> 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 deleting nodes
• Confusing mirror with sorting nodes
• Assuming mirror changes node values

2. Which Rust code snippet correctly swaps the left and right children of a binary tree node?

easy

A. let temp = node.left.take(); node.left = node.right.take(); node.right = temp;

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

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

D. node.left = None; node.right = None;

Solution

1. Step 1: Understand Rust ownership for swapping

   In Rust, to swap children, we must take ownership using take() to avoid borrowing issues.

2. Step 2: Analyze the code snippets

   let temp = node.left.take(); node.left = node.right.take(); node.right = temp; uses take() to temporarily hold left child, then swaps left and right correctly. node.left = node.right; node.right = node.left; incorrectly assigns right to left and then left to right without temp, causing both to be same.

3. Final Answer:

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

4. Quick Check:

   Use take() to swap safely [OK]

Hint: Use take() to swap children safely in Rust [OK]

Common Mistakes:

• Assigning children without temporary variable
• Not using take() causing borrow errors
• Setting children to None accidentally

3. Given the Rust code below that mirrors a binary tree, what is the output when printed in-order?

struct Node {
    val: i32,
    left: Option,
    right: Option,
}

fn mirror(node: &mut Option) {
    if let Some(n) = node {
        mirror(&mut n.left);
        mirror(&mut n.right);
        let temp = n.left.take();
        n.left = n.right.take();
        n.right = temp;
    }
}

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

// In-order traversal after mirror?

medium

A. [3, 5, 1, 2, 4]

B. [4, 2, 1, 3, 5]

C. [1, 2, 3, 4, 5]

D. [5, 3, 1, 4, 2]

Solution

1. Step 1: Understand the original tree and mirror effect

   Original tree in-order: left, root, right = [4, 2, 1, 3, 5]. Mirror swaps left and right children at every node.

2. Step 2: Perform mirror and in-order traversal

   After mirror, tree structure:
   1
   / \ 3 2 / \ 5 4 In-order traversal now: left(3 subtree), root(1), right(2 subtree) = [5, 3, 1, 4, 2]

3. Final Answer:

   [5, 3, 1, 4, 2] -> Option D

4. Quick Check:

   Mirror flips children, in-order changes accordingly [OK]

Hint: Mirror flips children; in-order reverses subtrees [OK]

Common Mistakes:

• Not swapping children before traversal
• Confusing pre-order with in-order traversal
• Assuming in-order stays same after mirror

4. The following Rust function is intended to mirror a binary tree but has a bug. What is the bug?

fn mirror(node: &mut Option) {
    if let Some(n) = node {
        mirror(&mut n.left);
        mirror(&mut n.right);
        n.left = n.right.take();
        n.right = n.left.take();
    }
}

medium

A. Using immutable borrow instead of mutable borrow

B. Missing base case for empty node

C. Swapping children incorrectly causes both to be None

D. Recursion order is wrong

Solution

1. Step 1: Analyze the swapping lines

   The code assigns n.left = n.right.take() first, which moves right child to left and sets right to None. Then n.right = n.left.take() tries to take from left, which is now the old right child, but after first take, left is already moved, so it becomes None.

2. Step 2: Identify the bug

   Both children end up None because the second take is from a moved value. Correct approach is to use a temporary variable to hold one child before swapping.

3. Final Answer:

   Swapping children incorrectly causes both to be None -> Option C

4. Quick Check:

   Swap needs temp variable to avoid losing nodes [OK]

Hint: Use temp variable to swap children safely [OK]

Common Mistakes:

• Swapping without temp causes data loss
• Ignoring ownership rules in Rust
• Assuming recursion order fixes swap

5. You want to mirror a binary tree and then print its level order traversal. Which approach correctly combines mirroring and level order traversal in Rust?

hard

A. Print level order first, then mirror the tree recursively

B. First mirror the tree recursively, then use a queue to print nodes level by level

C. Mirror the tree by swapping values only, then print in-order traversal

D. Use recursion to print level order while mirroring simultaneously

Solution

1. Step 1: Understand the correct order of operations

   Mirroring must be done first to change the tree structure. Then level order traversal prints nodes level by level using a queue.

2. Step 2: Analyze options

   First mirror the tree recursively, then use a queue to print nodes level by level correctly mirrors recursively first, then then uses a queue for level order. Print level order first, then mirror the tree recursively prints before mirror, so output is original. Mirror the tree by swapping values only, then print in-order traversal swaps values only, not structure. Use recursion to print level order while mirroring simultaneously tries recursion for level order which is not straightforward.

3. Final Answer:

   First mirror the tree recursively, then use a queue to print nodes level by level -> Option B

4. Quick Check:

   Mirror first, then level order with queue [OK]

Hint: Mirror tree first, then use queue for level order [OK]

Common Mistakes:

• Printing before mirroring
• Trying to print level order recursively
• Swapping values instead of nodes