Mirror a Binary Tree in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap the left and right child nodes of the root.

DSA Rust

fn mirror(root: &mut Option<Box<TreeNode>>) {
    if let Some(node) = root.as_mut() {
        let temp = node.left.take();
        node.left = node.right.take();
        node.right = [1];
    }
}

Drag options to blanks, or click blank then click option'

Atemp

Bnode.left

Cnode.right

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning node.left to node.right without using a temporary variable causes loss of data.

Using None instead of temp loses the original left subtree.

We store the original left child in temp, then assign the right child to left, and finally assign temp to right to complete the swap.

2fill in blank

medium

Complete the code to recursively mirror the left subtree.

DSA Rust

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

// Call mirror on the root
mirror(&mut [1]);

Drag options to blanks, or click blank then click option'

Aroot

Bnode

Ctemp

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Passing node instead of root causes errors because node is not in scope here.

Passing None does nothing.

The function mirror is called on the root node to start the mirroring process from the top.

3fill in blank

hard

Fix the error in the code to correctly mirror the binary tree.

DSA Rust

fn mirror(root: &mut Option<Box<TreeNode>>) {
    if root.is_none() {
        return;
    }
    let node = root.as_mut().unwrap();
    mirror(&mut node.left);
    mirror(&mut node.right);
    let temp = node.left.take();
    node.left = node.right.take();
    node.right = [1];
}

Drag options to blanks, or click blank then click option'

Anode.right

BNone

Cnode.left

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning node.right to node.left causes incorrect swapping.

Assigning None loses the subtree.

The variable temp holds the original left subtree and must be assigned to node.right to complete the swap.

4fill in blank

hard

Fill both blanks to create a function that mirrors a binary tree recursively.

DSA Rust

fn mirror(root: &mut Option<Box<TreeNode>>) {
    if [1] {
        return;
    }
    let node = root.as_mut().unwrap();
    mirror(&mut node.left);
    mirror(&mut node.right);
    let temp = node.left.take();
    node.left = node.right.take();
    node.right = [2];
}

Drag options to blanks, or click blank then click option'

Aroot.is_none()

Broot.is_some()

Ctemp

Dnode.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using root.is_some() in the if condition causes the function to return too early.

Assigning node.right to node.left instead of temp causes incorrect swapping.

The function returns immediately if the root is None (empty tree). Then it swaps left and right children using temp.

5fill in blank

hard

Fill all three blanks to implement a complete mirror function for a binary tree.

DSA Rust

fn mirror(root: &mut Option<Box<TreeNode>>) {
    if [1] {
        return;
    }
    let node = root.as_mut().unwrap();
    mirror(&mut [2]);
    mirror(&mut [3]);
    let temp = node.left.take();
    node.left = node.right.take();
    node.right = temp;
}

Drag options to blanks, or click blank then click option'

Aroot.is_none()

Bnode.left

Cnode.right

Droot.is_some()

Attempts:

3 left

💡 Hint

Common Mistakes

Calling mirror on root instead of node's children causes infinite recursion.

Swapping children before recursive calls leads to incorrect results.

The function returns if the tree is empty. Then it recursively mirrors left and right subtrees before swapping them.

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