Mirror a Binary Tree in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Mirroring a Simple Binary Tree

What is the output of the following Rust code that mirrors a binary tree and then prints its inorder traversal?

DSA Rust

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

#[derive(Debug)]
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(root: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        let mut node_borrow = node.borrow_mut();
        let left = node_borrow.left.take();
        let right = node_borrow.right.take();
        node_borrow.left = right;
        node_borrow.right = left;
        drop(node_borrow);
        mirror(node.borrow().left.clone());
        mirror(node.borrow().right.clone());
    }
}

fn inorder(root: Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(node.borrow().left.clone(), vals);
        vals.push(node.borrow().val);
        inorder(node.borrow().right.clone(), vals);
    }
}

fn main() {
    let root = TreeNode::new(1);
    root.borrow_mut().left = Some(TreeNode::new(2));
    root.borrow_mut().right = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(4));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(5));

    mirror(Some(root.clone()));

    let mut vals = vec![];
    inorder(Some(root), &mut vals);
    println!("{:?}", vals);
}

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

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

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

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

💡 Hint

Think about how the left and right children are swapped at every node before recursive calls.

Mirroring swaps left and right children at every node. The original inorder traversal is [4, 2, 5, 1, 3]. After mirroring, the tree structure changes, and the inorder traversal becomes [3, 1, 5, 2, 4].

🧠 Conceptual

intermediate

Understanding Mirror Operation on Binary Trees

Which of the following statements correctly describes the effect of mirroring a binary tree?

A Mirroring a binary tree sorts the nodes in ascending order.

B Mirroring a binary tree swaps the left and right children of every node recursively.

C Mirroring a binary tree reverses the values of nodes in inorder traversal only.

D Mirroring a binary tree removes all leaf nodes.

💡 Hint

Focus on what happens to the children of each node during mirroring.

Mirroring means swapping the left and right children of every node in the tree recursively. It does not change node values or remove nodes.

🔧 Debug

advanced

Identify the Bug in Mirror Function

What error will the following Rust code produce when trying to mirror a binary tree?

DSA Rust

fn mirror(root: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        let mut node_borrow = node.borrow_mut();
        let left = node_borrow.left.clone();
        let right = node_borrow.right.clone();
        node_borrow.left = right;
        node_borrow.right = left;
        mirror(node_borrow.left.clone());
        mirror(node_borrow.right.clone());
    }
}

A Runtime panic due to borrowing rules violation

B Compile error: cannot move out of borrowed content

C Stack overflow due to infinite recursion

D No error, works correctly

💡 Hint

Consider Rust's borrowing rules when mutably borrowing and then recursively calling mirror.

The code borrows node mutably and then tries to borrow it again recursively without releasing the mutable borrow, causing a runtime panic due to borrowing rules violation.

❓ Predict Output

advanced

Output After Mirroring a Complex Tree

Given the following binary tree structure and mirror function, what is the preorder traversal output after mirroring?

DSA Rust

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

#[derive(Debug)]
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(root: Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        let mut node_borrow = node.borrow_mut();
        let left = node_borrow.left.take();
        let right = node_borrow.right.take();
        node_borrow.left = right;
        node_borrow.right = left;
        drop(node_borrow);
        mirror(node.borrow().left.clone());
        mirror(node.borrow().right.clone());
    }
}

fn preorder(root: Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        vals.push(node.borrow().val);
        preorder(node.borrow().left.clone(), vals);
        preorder(node.borrow().right.clone(), vals);
    }
}

fn main() {
    let root = TreeNode::new(10);
    root.borrow_mut().left = Some(TreeNode::new(5));
    root.borrow_mut().right = Some(TreeNode::new(15));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().left = Some(TreeNode::new(3));
    root.borrow_mut().left.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(7));
    root.borrow_mut().right.as_ref().unwrap().borrow_mut().right = Some(TreeNode::new(18));

    mirror(Some(root.clone()));

    let mut vals = vec![];
    preorder(Some(root), &mut vals);
    println!("{:?}", vals);
}

A [10, 5, 3, 7, 15, 18]

B [10, 5, 7, 3, 15, 18]

C [10, 15, 7, 3, 5, 18]

D [10, 15, 18, 5, 7, 3]

💡 Hint

Preorder traversal visits root, then left subtree, then right subtree. Mirroring swaps left and right children.

After mirroring, left and right children are swapped at every node. The preorder traversal visits nodes in the order: root, right subtree (original left), left subtree (original right).

🧠 Conceptual

expert

Effect of Mirroring on Tree Height and Structure

After mirroring a binary tree, which of the following statements is always true?

A The height of the tree remains the same, but the left and right subtrees of every node are swapped.

B The number of leaf nodes decreases by half.

C The tree becomes a complete binary tree regardless of its original shape.

D The height of the tree doubles because the tree becomes skewed.

💡 Hint

Mirroring only swaps children, it does not add or remove nodes.

Mirroring swaps left and right children at every node but does not change the height or number of nodes. The structure is mirrored but height remains unchanged.

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