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

Concept Flow - Check if Two Trees are Symmetric

Start with two root nodes

↓

Are both nodes nil?

Yes→Return True

No↓

Is one node nil?

Yes→Return False

No↓

Do nodes have same value?

No→Return False

Yes↓

Check left subtree of first with right subtree of second

↓

Check right subtree of first with left subtree of second

↓

Return True if both checks True, else False

The function compares two trees node-by-node to check if they are mirror images, returning true only if all corresponding nodes match symmetrically.

Execution Sample

DSA Go

func isSymmetric(t1, t2 *TreeNode) bool {
  if t1 == nil && t2 == nil { return true }
  if t1 == nil || t2 == nil { return false }
  return t1.Val == t2.Val && isSymmetric(t1.Left, t2.Right) && isSymmetric(t1.Right, t2.Left)
}

This code checks if two trees are symmetric by recursively comparing nodes in mirrored positions.

Execution Table

Step	t1.Val	t2.Val	Condition Checked	Result	Next Action
1	1	1	Both nil? No	Continue	Check values
2	1	1	One nil? No	Continue	Compare values
3	1	1	Values equal? Yes	Continue	Check left-right and right-left subtrees
4	2	2	Both nil? No	Continue	Check values
5	2	2	One nil? No	Continue	Compare values
6	2	2	Values equal? Yes	Continue	Check left-right and right-left subtrees
7	nil	nil	Both nil? Yes	Return True	Back to previous call
8	nil	nil	Both nil? Yes	Return True	Back to previous call
9	3	3	Both nil? No	Continue	Check values
10	3	3	One nil? No	Continue	Compare values
11	3	3	Values equal? Yes	Continue	Check left-right and right-left subtrees
12	nil	nil	Both nil? Yes	Return True	Back to previous call
13	nil	nil	Both nil? Yes	Return True	Back to previous call
14	All recursive calls returned True			Return True	Trees are symmetric
15			Exit		All checks passed

💡 All corresponding nodes matched symmetrically, so the trees are symmetric.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 11	Final
t1.Val	1	2	3	3	N/A
t2.Val	1	2	3	3	N/A
Return Value	N/A	N/A	N/A	N/A	True

Key Moments - 3 Insights

Why do we check if both nodes are nil first?

Because if both nodes are nil, it means the subtrees are empty and symmetric at this point (see steps 7, 8, 12, 13 in execution_table).

What happens if one node is nil but the other is not?

The trees are not symmetric because one side has a node while the other does not (see step 5 condition 'One nil? No' means if it was Yes, return false).

Why do we compare t1.Left with t2.Right and t1.Right with t2.Left?

Because symmetry means the left subtree of one tree mirrors the right subtree of the other, so we check these pairs recursively (see step 3 and 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the result of the condition 'Both nil?' at step 7?

A Not checked

B False

C True

D Error

💡 Hint

Check the 'Condition Checked' and 'Result' columns at step 7 in execution_table.

At which step does the function confirm that node values are equal for the first time?

A Step 3

B Step 1

C Step 6

D Step 10

💡 Hint

Look for 'Values equal? Yes' in the 'Condition Checked' column in execution_table.

If t1.Left was nil but t2.Right was not, what would happen in the execution?

A Return True

B Return False

C Continue checking

D Cause an error

💡 Hint

Refer to the key moment about one node being nil and the other not, and the condition 'One nil?' in execution_table.

Concept Snapshot

Check if Two Trees are Symmetric:
- Compare two nodes: if both nil, return true
- If one nil, return false
- Check if values equal
- Recursively check left of one with right of other and vice versa
- Return true only if all checks pass

Full Transcript

This concept shows how to check if two trees are mirror images. We start by comparing the root nodes. If both are empty, they are symmetric here. If only one is empty, they are not symmetric. If both have values, we check if the values match. Then we recursively check the left subtree of the first tree against the right subtree of the second tree, and the right subtree of the first tree against the left subtree of the second tree. If all these checks return true, the trees are symmetric. The execution table traces these steps carefully, showing conditions and results at each step.

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 around the center.

2. Step 2: Compare structure and node 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 [OK]

Hint: Symmetric trees mirror each other exactly [OK]

Common Mistakes:

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

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

easy

A. func isSymmetric(t1 *TreeNode) bool

B. func isSymmetric(t1 TreeNode, t2 TreeNode) int

C. func isSymmetric(t1 *TreeNode, t2 *TreeNode) bool

D. func isSymmetric(t1 *TreeNode, t2 *TreeNode) string

Solution

1. Step 1: Identify correct parameter types

   Function should take pointers to TreeNode structs for both trees to compare.

2. Step 2: Identify correct return type

   Return type should be bool to indicate symmetric (true) or not (false).

3. Final Answer:

   func isSymmetric(t1 *TreeNode, t2 *TreeNode) bool -> Option C

4. Quick Check:

   Pointer params and bool return [OK]

Hint: Use pointers and bool return for tree comparison [OK]

Common Mistakes:

• Using value instead of pointer for trees
• Returning int or string instead of bool
• Missing one tree parameter

3. What will be the output of the following Go code snippet?

package main
import "fmt"

type TreeNode struct {
    Val int
    Left, Right *TreeNode
}

func isSymmetric(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return t1.Val == t2.Val && isSymmetric(t1.Left, t2.Right) && isSymmetric(t1.Right, t2.Left)
}

func main() {
    root1 := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 2}}
    root2 := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}
    fmt.Println(isSymmetric(root1, root2))
}

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Compare root nodes

   Both roots have value 1, so check children.

2. Step 2: Compare left and right subtrees

   Left subtree of root1 has value 2, right subtree of root2 has value 3, which differ.

3. Final Answer:

   false -> Option B

4. Quick Check:

   Different child values mean not symmetric [OK]

Hint: Check mirrored child values for symmetry [OK]

Common Mistakes:

• Assuming same root means symmetric
• Ignoring mismatch in child nodes
• Confusing symmetric with identical

4. Identify the bug in the following Go function that checks if two trees are symmetric:

func isSymmetric(t1, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return t1.Val == t2.Val && isSymmetric(t1.Left, t2.Left) && isSymmetric(t1.Right, t2.Right)
}

medium

A. The function does not check root node values.

B. The base case for nil nodes is missing.

C. The function should return int, not bool.

D. The recursive calls compare wrong child nodes for symmetry.

Solution

1. Step 1: Check recursive calls for symmetry

   Symmetry requires comparing left of one tree with right of the other, but code compares left with left and right with right.

2. Step 2: Identify correct recursive calls

   Correct calls should be isSymmetric(t1.Left, t2.Right) and isSymmetric(t1.Right, t2.Left).

3. Final Answer:

   The recursive calls compare wrong child nodes for symmetry. -> Option D

4. Quick Check:

   Mirror children must be compared [OK]

Hint: Compare left with right child for symmetry [OK]

Common Mistakes:

• Comparing left with left and right with right
• Missing nil base cases
• Returning wrong type

5. Given two binary trees, write a Go function to check if they are symmetric. Which approach correctly handles the edge case where one tree is nil and the other is not?

hard

A. Return false immediately if one tree is nil and the other is not.

B. Return true if one tree is nil and the other is not.

C. Ignore nil checks and compare node values only.

D. Return true if both trees have the same number of nodes.

Solution

1. Step 1: Handle nil tree edge cases

   If one tree is nil and the other is not, they cannot be symmetric, so return false immediately.

2. Step 2: Ensure correct base cases in recursion

   Only return true if both trees are nil at the same time, otherwise false.

3. Final Answer:

   Return false immediately if one tree is nil and the other is not. -> Option A

4. Quick Check:

   Nil mismatch means not symmetric [OK]

Hint: Check nil mismatch first to avoid errors [OK]

Common Mistakes:

• Returning true when one tree is nil
• Skipping nil checks causing runtime errors
• Comparing only node counts