Mirror a Binary Tree in DSA Rust - Build from Scratch

Mirror a Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to create a mirror image of this tree, swapping left and right children at every node.

🎯 Goal: Build a Rust program that creates a binary tree, then mirrors it by swapping left and right children recursively, and finally prints the mirrored tree in order.

📋 What You'll Learn

Define a binary tree node struct called TreeNode with value, left, and right fields

Create a sample binary tree with exact values: root 1, left child 2, right child 3, left child of 2 is 4, right child of 2 is 5

Write a function mirror that takes a mutable reference to a TreeNode and swaps its left and right children recursively

Write a function inorder_print that prints the tree nodes in order separated by spaces

Print the mirrored tree using inorder_print

💡 Why This Matters

🌍 Real World

Mirroring trees is useful in graphics, image processing, and reversing hierarchical data structures.

💼 Career

Understanding tree manipulations is important for software engineering roles involving data structures, algorithms, and system design.

1

Create the binary tree structure and initial tree

Define a struct called TreeNode with fields value: i32, left: Option>, and right: Option>. Then create a variable root representing this tree:
1
/ \
2 3
/ \
4 5
Use Some(Box::new(TreeNode { ... })) to build the tree exactly as shown.

DSA Rust

# Define TreeNode struct and create the root tree
# Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Add the mirror function to swap children

Write a function called mirror that takes a mutable reference node: &mut Option>. If the node is Some, recursively call mirror on its left and right children, then swap the left and right children.

DSA Rust

struct TreeNode {
    value: i32,
    left: Option>,
    right: Option>,
}

fn mirror(node: &mut Option>) {
    // Your code here
}

fn main() {
    let root = Some(Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode { value: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { value: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { value: 3, left: None, right: None })),
    }));
}

Hint

Use Option::take() to swap children safely.

3

Add inorder print function to display tree nodes

Write a function called inorder_print that takes a reference node: &Option>. It should recursively print the left subtree, then the current node's value followed by a space, then the right subtree.

DSA Rust

struct TreeNode {
    value: i32,
    left: Option>,
    right: Option>,
}

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

fn inorder_print(node: &Option>) {
    // Your code here
}

fn main() {
    let root = Some(Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode { value: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { value: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { value: 3, left: None, right: None })),
    }));
}

Hint

Use recursion to print left subtree, then node value, then right subtree.

4

Mirror the tree and print the mirrored tree

In main, make root mutable. Call mirror(&mut root) to mirror the tree. Then call inorder_print(&root) to print the mirrored tree nodes in order.

DSA Rust

struct TreeNode {
    value: i32,
    left: Option>,
    right: Option>,
}

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

fn inorder_print(node: &Option>) {
    if let Some(ref n) = node {
        inorder_print(&n.left);
        print!("{} ", n.value);
        inorder_print(&n.right);
    }
}

fn main() {
    let mut root = Some(Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: Some(Box::new(TreeNode { value: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { value: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode { value: 3, left: None, right: None })),
    }));
    // Your code here
}

Hint

Make root mutable, call mirror(&mut root), then inorder_print(&root).

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