Mirror a Binary Tree in DSA Rust

Mental Model

Flip the tree so left and right children swap places at every node.

Analogy: Imagine holding a tree in front of a mirror; the left side becomes the right side and vice versa.

    1
   / \
  2   3
 /     \
4       5

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has left child 4; 3 has right child 5

Goal: Transform the tree so left and right children are swapped at every node

Step 1: Start at root node 1, swap left and right children

    1
   / \
  3   2
 /     \
5       4

Why: Swapping children at root flips the top level branches

Step 2: Move to left child (3), swap its children

    1
   / \
  3   2
 /     \
5       4

Why: 3 had right child 5, swapping makes it left child

Step 3: Move to right child (2), swap its children

    1
   / \
  3   2
 /     \
5       4

Why: 2 had left child 4, swapping makes it right child

Step 4: Leaf nodes 5 and 4 have no children, no swaps needed

    1
   / \
  3   2
 /     \
5       4

Why: Leaves remain the same after swapping null children

Result:

    1
   / \
  3   2
 /     \
5       4

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn mirror_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
    if let Some(node_rc) = root {
        let mut node = node_rc.borrow_mut();
        // Swap left and right children
        let temp = node.left.take();
        node.left = mirror_tree(node.right.take());
        node.right = mirror_tree(temp);
        drop(node); // release borrow
        Some(node_rc)
    } else {
        None
    }
}

fn print_tree(root: &Option<Rc<RefCell<TreeNode>>>, prefix: String, is_left: bool) {
    if let Some(node_rc) = root {
        let node = node_rc.borrow();
        println!("{}{}{}", prefix, if is_left {"├── "} else {"└── "}, node.val);
        let new_prefix = format!("{}{}", prefix, if is_left {"│   "} else {"    "});
        print_tree(&node.left, new_prefix.clone(), true);
        print_tree(&node.right, new_prefix, false);
    }
}

fn main() {
    // Build tree:
    //     1
    //    / \
    //   2   3
    //  /     \
    // 4       5
    let root = TreeNode::new(1);
    {
        let mut r = root.borrow_mut();
        r.left = Some(TreeNode::new(2));
        r.right = Some(TreeNode::new(3));
    }
    {
        let left = root.borrow().left.clone().unwrap();
        let mut l = left.borrow_mut();
        l.left = Some(TreeNode::new(4));
    }
    {
        let right = root.borrow().right.clone().unwrap();
        let mut r = right.borrow_mut();
        r.right = Some(TreeNode::new(5));
    }

    println!("Original tree:");
    print_tree(&Some(root.clone()), String::new(), false);

    let mirrored = mirror_tree(Some(root));

    println!("\nMirrored tree:");
    print_tree(&mirrored, String::new(), false);
}

if let Some(node_rc) = root {

check if current node exists to process

let mut node = node_rc.borrow_mut();

borrow node mutably to swap children

let temp = node.left.take();

temporarily save left child and remove it

node.left = mirror_tree(node.right.take());

recursively mirror right subtree and assign to left

node.right = mirror_tree(temp);

recursively mirror saved left subtree and assign to right

Some(node_rc)

return current node after swapping children

Output

Original tree:

└── 1

    ├── 2

    │   ├── 4

    │   └── 

    └── 3

        ├── 

        └── 5



Mirrored tree:

└── 1

    ├── 3

    │   ├── 5

    │   └── 

    └── 2

        ├── 

        └── 4

Complexity Analysis

Time: O(n) because each node is visited once to swap children

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Iterative approaches exist but recursion is simpler and clearer for tree traversal

Edge Cases

Empty tree (root is None)

Returns None immediately without error

DSA Rust

if let Some(node_rc) = root {

Single node tree

Returns the same single node as mirror has no effect

DSA Rust

if let Some(node_rc) = root {

Tree with only left or only right children

Children get swapped correctly, flipping the tree structure

DSA Rust

node.left = mirror_tree(node.right.take());

When to Use This Pattern

When asked to flip or invert a binary tree, use the mirror pattern by swapping left and right children recursively.

Common Mistakes

Mistake: Swapping children without recursive calls, so only root swaps but subtrees remain unchanged
Fix: Recursively call mirror function on children before swapping to flip entire tree

Mistake: Not handling None children properly causing runtime errors
Fix: Check for None before recursive calls and handle base case returning None

Summary

It flips a binary tree by swapping left and right children at every node.

Use it when you need the mirror image of a binary tree structure.

The key is to recursively swap children bottom-up to flip the whole tree.

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