Check if Two Trees are Symmetric in DSA Rust

Mental Model

Two trees are symmetric if one is the mirror image of the other, meaning their structures and values reflect each other perfectly.

Analogy: Imagine holding two identical tree-shaped ornaments facing each other; if one is the exact mirror reflection of the other, they are symmetric.

Tree1:       1           Tree2:       1
           /   \                   /   \
          2     3                 3     2
         /       \               /       \
        4         5             5         4

Symmetry means Tree1's left subtree matches Tree2's right subtree and vice versa.

Dry Run Walkthrough

Input: Tree1: 1 -> 2 -> 4, 3 -> 5; Tree2: 1 -> 3 -> 5, 2 -> 4

Goal: Check if Tree2 is the mirror image of Tree1

Step 1: Compare roots of both trees (1 and 1)

Tree1 root=1 ↑, Tree2 root=1 ↑

Why: Roots must be equal for symmetry

Step 2: Compare left child of Tree1 (2) with right child of Tree2 (2)

Tree1 left=2 ↑, Tree2 right=2 ↑

Why: Left subtree of Tree1 should mirror right subtree of Tree2

Step 3: Compare right child of Tree1 (3) with left child of Tree2 (3)

Tree1 right=3 ↑, Tree2 left=3 ↑

Why: Right subtree of Tree1 should mirror left subtree of Tree2

Step 4: Compare left child of Tree1's left (4) with right child of Tree2's right (4)

Tree1 left.left=4 ↑, Tree2 right.right=4 ↑

Why: Mirror nodes must have equal values

Step 5: Compare right child of Tree1's right (5) with left child of Tree2's left (5)

Tree1 right.right=5 ↑, Tree2 left.left=5 ↑

Why: Mirror nodes must have equal values

Result:

Trees are symmetric because all mirrored nodes match in value and structure.

Annotated Code

DSA Rust

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

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

impl TreeNode {
    pub 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, // both empty means symmetric
        (Some(n1), Some(n2)) => {
            let n1 = n1.borrow();
            let n2 = n2.borrow();
            // values must match and left subtree of n1 mirrors right subtree of n2 and vice versa
            n1.val == n2.val &&
            is_symmetric(n1.left.clone(), n2.right.clone()) &&
            is_symmetric(n1.right.clone(), n2.left.clone())
        },
        _ => false, // one empty, one not means not symmetric
    }
}

fn main() {
    // Build Tree1
    let node4 = Rc::new(RefCell::new(TreeNode::new(4)));
    let node5 = Rc::new(RefCell::new(TreeNode::new(5)));
    let node2 = Rc::new(RefCell::new(TreeNode::new(2)));
    node2.borrow_mut().left = Some(node4.clone());
    let node3 = Rc::new(RefCell::new(TreeNode::new(3)));
    node3.borrow_mut().right = Some(node5.clone());
    let root1 = Rc::new(RefCell::new(TreeNode::new(1)));
    root1.borrow_mut().left = Some(node2.clone());
    root1.borrow_mut().right = Some(node3.clone());

    // Build Tree2 (mirror of Tree1)
    let node4_b = Rc::new(RefCell::new(TreeNode::new(4)));
    let node5_b = Rc::new(RefCell::new(TreeNode::new(5)));
    let node2_b = Rc::new(RefCell::new(TreeNode::new(2)));
    node2_b.borrow_mut().right = Some(node4_b.clone());
    let node3_b = Rc::new(RefCell::new(TreeNode::new(3)));
    node3_b.borrow_mut().left = Some(node5_b.clone());
    let root2 = Rc::new(RefCell::new(TreeNode::new(1)));
    root2.borrow_mut().left = Some(node3_b.clone());
    root2.borrow_mut().right = Some(node2_b.clone());

    let result = is_symmetric(Some(root1), Some(root2));
    println!("{}", result);
}

match (t1, t2) {

check if both nodes are None or Some

(None, None) => true,

both empty means symmetric at this subtree

(Some(n1), Some(n2)) => {

both nodes present, compare values and recurse

n1.val == n2.val && is_symmetric(n1.left.clone(), n2.right.clone()) && is_symmetric(n1.right.clone(), n2.left.clone())

values must match and left subtree of one mirrors right subtree of other

_ => false,

one node empty and other not means not symmetric

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to compare symmetry

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

vs Alternative: Compared to iterative or naive approaches, this recursive mirror check is clean and efficient with minimal overhead

Edge Cases

Both trees empty

Returns true since empty trees are symmetric

DSA Rust

(None, None) => true,

One tree empty, other not

Returns false because structure differs

DSA Rust

_ => false,

Trees with single node each, same value

Returns true as single nodes mirror each other

DSA Rust

n1.val == n2.val && is_symmetric(...)

When to Use This Pattern

When asked if two trees are mirror images or symmetric, use a recursive check comparing left subtree of one to right subtree of the other.

Common Mistakes

Mistake: Comparing left subtree to left subtree instead of left to right
Fix: Compare left subtree of first tree with right subtree of second tree and vice versa

Summary

Checks if two trees are mirror images by comparing nodes recursively.

Use when verifying if two trees are symmetric in structure and values.

The key is to compare left subtree of one tree with right subtree of the other.

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