Check if Two Trees are Symmetric in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of symmetric tree check function

What is the output of the following Rust code that checks if two binary trees are symmetric?

DSA Rust

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

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

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

fn is_symmetric(t1: Option<Rc<RefCell<TreeNode>>>, t2: Option<Rc<RefCell<TreeNode>>>) -> bool {
    match (t1, t2) {
        (None, None) => true,
        (Some(n1), Some(n2)) => {
            let n1 = n1.borrow();
            let n2 = n2.borrow();
            n1.val == n2.val &&
            is_symmetric(n1.left.clone(), n2.right.clone()) &&
            is_symmetric(n1.right.clone(), n2.left.clone())
        },
        _ => false,
    }
}

fn main() {
    let left = Rc::new(RefCell::new(TreeNode::new(2)));
    left.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(3))));
    left.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(4))));

    let right = Rc::new(RefCell::new(TreeNode::new(2)));
    right.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    right.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(3))));

    println!("{}", is_symmetric(Some(left), Some(right)));
}

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Check if the values and the mirrored children match recursively.

The function recursively compares the values of nodes and their mirrored children. The two trees are symmetric because left subtree of one matches right subtree of the other and vice versa.

❓ Predict Output

intermediate

Output when one tree is None

What is the output of the following Rust code when checking symmetry between a tree and None?

DSA Rust

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

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

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

fn is_symmetric(t1: Option<Rc<RefCell<TreeNode>>>, t2: Option<Rc<RefCell<TreeNode>>>) -> bool {
    match (t1, t2) {
        (None, None) => true,
        (Some(n1), Some(n2)) => {
            let n1 = n1.borrow();
            let n2 = n2.borrow();
            n1.val == n2.val &&
            is_symmetric(n1.left.clone(), n2.right.clone()) &&
            is_symmetric(n1.right.clone(), n2.left.clone())
        },
        _ => false,
    }
}

fn main() {
    let tree = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    let none_tree: Option<Rc<RefCell<TreeNode>>> = None;
    println!("{}", is_symmetric(tree, none_tree));
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

One tree is None, the other is not.

The function returns false if one tree is None and the other is not, so output is false.

🔧 Debug

advanced

Identify the error in symmetric check function

What error will this Rust code produce when checking symmetry of two trees?

DSA Rust

fn is_symmetric(t1: Option<Rc<RefCell<TreeNode>>>, t2: Option<Rc<RefCell<TreeNode>>>) -> bool {
    match (t1, t2) {
        (None, None) => true,
        (Some(n1), Some(n2)) => {
            let n1 = n1.borrow();
            let n2 = n2.borrow();
            n1.val == n2.val &&
            is_symmetric(n1.left.clone(), n2.left.clone()) &&
            is_symmetric(n1.right.clone(), n2.right.clone())
        },
        _ => false,
    }
}

A Returns true for symmetric trees

B Runtime panic

C Compilation error

D Returns false for symmetric trees

💡 Hint

Check if the recursive calls compare mirrored children correctly.

The code compares left with left and right with right, not mirrored children, so it returns false for symmetric trees.

🧠 Conceptual

advanced

Which property must hold for two trees to be symmetric?

For two binary trees to be symmetric, which condition must be true?

A Root values are equal and left subtree of first equals right subtree of second, and right subtree of first equals left subtree of second

B Root values are equal and left subtree of first equals left subtree of second, and right subtree of first equals right subtree of second

C Both trees have the same number of nodes regardless of structure

D Both trees are complete binary trees

💡 Hint

Think about mirror image structure and values.

Symmetry means the left subtree of one tree matches the right subtree of the other and vice versa, with equal root values.

🚀 Application

expert

Number of recursive calls for symmetric check on balanced tree

Given a balanced binary tree of height h (root at height 0), how many total calls to is_symmetric are made when checking if the tree is symmetric with itself?

A 2^(h+1)

B 2^h - 1

C 2^(h+1) - 1

D 2^(h+2) - 2

💡 Hint

Each call compares a pair of nodes; the number of nodes in a full binary tree is 2^(h+1)-1.

The function compares pairs of nodes recursively. For a balanced tree of height h, total nodes are 2^(h+1)-1, so that many calls are made.

Practice

1. What does it mean for two binary trees to be symmetric?

easy

A. They are mirror images of each other around their center.

B. They have the same number of nodes.

C. They have the same root value only.

D. They have identical left subtrees only.

Solution

1. Step 1: Understand symmetry in trees

   Two trees are symmetric if one is the mirror reflection of the other, meaning left subtree of one matches right subtree of the other and vice versa.

2. Step 2: Compare structure and values

   Both structure and node values must match in a mirrored way for symmetry.

3. Final Answer:

   They are mirror images of each other around their center. -> Option A

4. Quick Check:

   Symmetry means mirror image = C [OK]

Hint: Symmetric trees mirror each other exactly [OK]

Common Mistakes:

• Thinking same number of nodes means symmetric
• Only comparing root values
• Ignoring subtree structure

2. Which Rust function signature correctly represents a function to check if two binary trees are symmetric?

easy

A. fn is_symmetric(t1: Option<TreeNode>, t2: Option<TreeNode>) -> bool

B. fn is_symmetric(t1: &Option, t2: &Option) -> bool

C. fn is_symmetric(t1: &TreeNode, t2: &TreeNode) -> Option<bool>

D. fn is_symmetric(t1: TreeNode, t2: TreeNode) -> bool

Solution

1. Step 1: Understand Rust tree node representation

   Binary trees in Rust are often represented as Option to handle empty nodes safely.

2. Step 2: Choose correct signature

   Passing references to Option avoids ownership issues and returns bool for symmetric check.

3. Final Answer:

   fn is_symmetric(t1: &Option, t2: &Option) -> bool -> Option B

4. Quick Check:

   Use references to Option and bool return [OK]

Hint: Use references to Option for tree nodes [OK]

Common Mistakes:

• Passing TreeNode by value causing ownership errors
• Returning Option<bool> instead of bool
• Using non-Option types for nullable nodes

3. Given the following Rust code snippet, what will be the output?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

fn is_mirror(t1: &Option, t2: &Option) -> bool {
    match (t1, t2) {
        (None, None) => true,
        (Some(n1), Some(n2)) => {
            n1.val == n2.val &&
            is_mirror(&n1.left, &n2.right) &&
            is_mirror(&n1.right, &n2.left)
        },
        _ => false,
    }
}

fn main() {
    let tree1 = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
        right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
    }));
    let tree2 = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
        right: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
    }));
    println!("{}", is_mirror(&tree1, &tree2));
}

medium

A. Runtime panic

B. false

C. Compilation error

D. true

Solution

1. Step 1: Analyze tree structure

   tree1 has root 1, left child 2, right child 3; tree2 has root 1, left child 3, right child 2.

2. Step 2: Check mirror condition

   Left subtree of tree1 (2) matches right subtree of tree2 (2), and right subtree of tree1 (3) matches left subtree of tree2 (3), values match.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Mirror check returns true [OK]

Hint: Mirror values and subtree positions must match [OK]

Common Mistakes:

• Confusing left and right subtree positions
• Assuming same structure means symmetric
• Ignoring node values in comparison

4. Identify the bug in this Rust function that checks if two trees are symmetric:

fn is_mirror(t1: &Option, t2: &Option) -> bool {
    if t1.is_none() && t2.is_none() {
        return true;
    }
    if t1.is_none() || t2.is_none() {
        return false;
    }
    let n1 = t1.as_ref().unwrap();
    let n2 = t2.as_ref().unwrap();
    n1.val == n2.val &&
    is_mirror(&n1.left, &n2.left) &&
    is_mirror(&n1.right, &n2.right)
}

medium

A. It compares left subtree with left subtree instead of left with right.

B. It unwraps Option without checking for None.

C. It returns false when both trees are empty.

D. It uses incorrect return type.

Solution

1. Step 1: Review subtree comparisons

   The function compares n1.left with n2.left and n1.right with n2.right, which checks for equality, not mirror symmetry.

2. Step 2: Identify correct mirror check

   For symmetry, n1.left should be compared with n2.right and n1.right with n2.left.

3. Final Answer:

   It compares left subtree with left subtree instead of left with right. -> Option A

4. Quick Check:

   Mirror check swaps left and right subtrees [OK]

Hint: Mirror check swaps left and right subtrees [OK]

Common Mistakes:

• Comparing left with left and right with right
• Forgetting to check both subtrees recursively
• Ignoring None cases

5. You want to check if a single binary tree is symmetric around its center. Which approach correctly uses the two-tree symmetric check function is_mirror to solve this?

hard

A. Call is_mirror(&root, &root) to compare the tree with itself.

B. Call is_mirror(&root.left, &root.left) to compare left subtree with itself.

C. Call is_mirror(&root.left, &root.right) to compare left and right subtrees.

D. Call is_mirror(&root.right, &root.right) to compare right subtree with itself.

Solution

1. Step 1: Understand single tree symmetry

   A tree is symmetric if its left subtree is a mirror of its right subtree.

2. Step 2: Use is_mirror function correctly

   Comparing root.left and root.right subtrees with is_mirror checks this mirror condition.

3. Final Answer:

   Call is_mirror(&root.left, &root.right) to compare left and right subtrees. -> Option C

4. Quick Check:

   Compare left and right subtrees for symmetry [OK]

Hint: Check left and right subtrees for mirror symmetry [OK]

Common Mistakes:

• Comparing tree with itself instead of subtrees
• Comparing left subtree with itself
• Comparing right subtree with itself