Check if Two Trees are Symmetric in DSA Rust - Execution Trace

Concept Flow - Check if Two Trees are Symmetric

Start with root nodes of both trees

↓

Check if both nodes are None?

Yes→Return True

No↓

Check if one node is None or values differ?

Yes→Return False

No↓

Recursively check left subtree of first with right subtree of second

↓

Recursively check right subtree of first with left subtree of second

↓

Return True if both recursive checks are True, else False

The flow compares nodes pairwise from two trees, checking symmetry by matching left subtree of one with right subtree of the other recursively.

Execution Sample

DSA Rust

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

This function checks if two trees are mirror images by comparing nodes and their subtrees recursively.

Execution Table

Step	Nodes Compared	Condition	Result	Next Action
1	Root1(1) & Root2(1)	Both Some, values equal?	True	Check left1 vs right2 and right1 vs left2
2	Left1(2) & Right2(2)	Both Some, values equal?	True	Check left1.left vs right2.right and left1.right vs right2.left
3	Left1.left(None) & Right2.right(None)	Both None?	True	Return True
4	Left1.right(None) & Right2.left(None)	Both None?	True	Return True
5	Right1(3) & Left2(3)	Both Some, values equal?	True	Check right1.left vs left2.right and right1.right vs left2.left
6	Right1.left(None) & Left2.right(None)	Both None?	True	Return True
7	Right1.right(None) & Left2.left(None)	Both None?	True	Return True
8	All recursive calls True	Final result	True	Trees are symmetric
9	If any mismatch found	Condition fails	False	Return False

💡 Execution stops when all node pairs are checked or a mismatch is found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	Final
t1 node	Root(1)	Left(2)	Left.left(None)	Right(3)	None
t2 node	Root(1)	Right(2)	Right.right(None)	Left(3)	None
Result	N/A	True	True	True	True

Key Moments - 3 Insights

Why do we compare left subtree of first tree with right subtree of second tree?

Because symmetry means mirror image, so left side of one tree matches right side of the other. See execution_table steps 2 and 5.

What happens if one node is None and the other is not?

The function returns False immediately, as shown in execution_table step 9, because trees can't be symmetric if one side is missing a node.

Why do we return True when both nodes are None?

Because empty subtrees are symmetric by definition. This is shown in execution_table steps 3, 4, 6, and 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result when comparing Left1.left and Right2.right nodes at step 3?

A True

B False

C None

D Error

💡 Hint

Check execution_table row with Step 3 under Result column.

At which step does the function confirm that all recursive calls returned True and trees are symmetric?

A Step 5

B Step 8

C Step 2

D Step 9

💡 Hint

Look for the step mentioning 'All recursive calls True' in execution_table.

If the value of Right1 node was different from Left2 node at step 5, what would be the result?

A True

B False

C Continue checking

D Return None

💡 Hint

Refer to execution_table step 9 about mismatch condition.

Concept Snapshot

Check if Two Trees are Symmetric:
- Compare nodes pairwise: left of one with right of other
- If both None, return True
- If one None or values differ, return False
- Recursively check subtrees
- Return True if all checks pass

Full Transcript

This concept checks if two trees are mirror images by comparing nodes recursively. Starting from the roots, it compares values and then checks left subtree of the first tree with right subtree of the second, and vice versa. If both nodes are None, it returns True. If one node is None or values differ, it returns False. The process continues recursively until all nodes are checked or a mismatch is found. The execution table shows step-by-step node comparisons and decisions. Variable tracker shows how nodes and results change during recursion. Key moments clarify why left is compared to right and handling of None nodes. The visual quiz tests understanding of these steps. The snapshot summarizes the approach in simple rules.

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