Mirror a Binary Tree in DSA Rust - Time & Space Complexity

Time Complexity: Mirror a Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to flip a binary tree so its left and right children swap places.

How does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn mirror_tree(node: &mut Option>) {
    if let Some(n) = node.as_mut() {
        mirror_tree(&mut n.left);
        mirror_tree(&mut n.right);
        std::mem::swap(&mut n.left, &mut n.right);
    }
}
    

This code flips the tree by swapping left and right children for every node recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls visiting each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

Each node is visited once to swap its children, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 swaps and recursive calls
100	About 100 swaps and recursive calls
1000	About 1000 swaps and recursive calls

Pattern observation: The time grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to mirror the tree grows in direct proportion to the number of nodes.

Common Mistake

[X] Wrong: "The time depends on the height of the tree only."

[OK] Correct: The function visits every node, not just along one path, so the total nodes matter more than height alone.

Interview Connect

Understanding this helps you reason about recursive tree problems and shows you can analyze how recursion scales with input size.

Self-Check

"What if we changed the code to use iteration with a stack instead of recursion? How would the time complexity change?"

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