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

Concept Flow - Check if Two Trees are Symmetric

Start with root nodes of both trees

↓

Are both nodes null?

Yes→Return True

No↓

Is one node null?

Yes→Return False

No↓

Do node values match?

No→Return False

Yes↓

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

↓

End

The flow compares nodes of two trees step-by-step to check if they are mirror images, returning false on mismatch or null asymmetry.

Execution Sample

DSA Typescript

function isSymmetric(t1: TreeNode | null, t2: TreeNode | null): boolean {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  if (t1.val !== t2.val) return false;
  return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
}

This function checks if two trees are symmetric by comparing nodes recursively.

Execution Table

Step	t1 Node Value	t2 Node Value	Condition Checked	Result	Action Taken
1	1	1	Both null? (No)	False	Continue
2	1	1	One null? (No)	False	Continue
3	1	1	Values equal? (Yes)	True	Recurse left-right and right-left
4	2	2	Both null? (No)	False	Continue
5	2	2	One null? (No)	False	Continue
6	2	2	Values equal? (Yes)	True	Recurse left-right and right-left
7	null	null	Both null? (Yes)	True	Return True
8	null	null	Both null? (Yes)	True	Return True
9	3	3	Both null? (No)	False	Continue
10	3	3	One null? (No)	False	Continue
11	3	3	Values equal? (Yes)	True	Recurse left-right and right-left
12	null	null	Both null? (Yes)	True	Return True
13	null	null	Both null? (Yes)	True	Return True
14	Return from recursion			True	Combine results
15	Return from recursion			True	Combine results
16	Return from recursion			True	Final result: Trees are symmetric

💡 All node pairs matched symmetrically or were both null, so function returns True.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 11	Final
t1 Node	Root(1)	Left(2)	Left null	Right(3)	null
t2 Node	Root(1)	Right(2)	Right null	Left(3)	null
Result	undefined	undefined	undefined	undefined	true

Key Moments - 3 Insights

Why do we check if both nodes are null first?

Because if both nodes are null, it means this part of the trees matches perfectly (see steps 7, 8, 12, 13 in execution_table). We return true immediately to stop further checks.

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

This means the trees are not symmetric at this point (see step 2 in execution_table). We return false immediately because one side has a node while the other does not.

Why do we compare t1.left with t2.right and t1.right with t2.left?

Because symmetry means one tree is a mirror image of the other. So left subtree of one matches right subtree of the other (see step 3 and recursive calls).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the condition checked and its result?

A Values are unequal, result False

B Both nodes are null, result True

C One node is null, result False

D Values are equal, result True

💡 Hint

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

At which step does the function confirm the final result that trees are symmetric?

A Step 16

B Step 14

C Step 11

D Step 6

💡 Hint

Look for the step with 'Final result' in the 'Action Taken' column in execution_table.

If t1.left was null but t2.right was not, what would happen in the execution?

A Return true immediately

B Continue recursion

C Return false immediately

D Ignore and check other nodes

💡 Hint

Refer to the key moment about one node null and the other not, and step 2 in execution_table.

Concept Snapshot

Check if Two Trees are Symmetric:
- Compare two nodes at a time.
- If both null, return true.
- If one null, return false.
- If values differ, return false.
- 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 symmetric by comparing nodes recursively. We start by checking if both nodes are null, which means symmetry at that point. If only one node is null, symmetry breaks and we return false. If both nodes exist, we compare their values. If values differ, return false. Otherwise, we recursively check the left subtree of the first tree with the right subtree of the second tree, and the right subtree of the first tree with the left subtree of the second tree. If all these checks return true, the trees are symmetric. The execution table traces these steps with node values and conditions checked. Variable tracker shows how nodes and results change during recursion. Key moments clarify common confusions about null checks and recursive comparisons. 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 root.

B. They have the same number of nodes.

C. They have the same values in the same order.

D. They are both balanced binary search trees.

Solution

1. Step 1: Understand symmetry in trees

   Two trees are symmetric if one is the mirror reflection of the other around the root node.

2. Step 2: Differentiate from other properties

   Having the same number of nodes or values in order does not guarantee symmetry; symmetry requires mirrored structure and values.

3. Final Answer:

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

4. Quick Check:

   Symmetry means mirror image = A [OK]

Hint: Symmetric trees mirror each other around the root [OK]

Common Mistakes:

• Confusing symmetry with identical trees
• Thinking same node count means symmetry
• Assuming balanced trees are always symmetric

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

easy

A. function symmetricCheck(root1: TreeNode, root2: TreeNode): void

B. function isSymmetric(root1: TreeNode, root2: TreeNode): boolean

C. function checkSymmetry(tree1: TreeNode, tree2: TreeNode): number

D. function isSymmetric(root: TreeNode): boolean

Solution

1. Step 1: Identify correct parameters and return type

   The function should take two tree roots and return a boolean indicating symmetry.

2. Step 2: Check function signature correctness

   function isSymmetric(root1: TreeNode, root2: TreeNode): boolean matches this: two TreeNode parameters and boolean return type.

3. Final Answer:

   function isSymmetric(root1: TreeNode, root2: TreeNode): boolean -> Option B

4. Quick Check:

   Two roots + boolean return = D [OK]

Hint: Symmetry check needs two roots and boolean output [OK]

Common Mistakes:

• Using only one root parameter
• Returning number instead of boolean
• Using void return type

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

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (t1.val === t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}

const tree1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
const tree2 = new TreeNode(1, new TreeNode(3), new TreeNode(2));
console.log(isMirror(tree1, tree2));

medium

A. SyntaxError

B. false

C. true

D. RuntimeError

Solution

1. Step 1: Understand the isMirror function logic

   It checks if two trees are mirror images by comparing root values and recursively checking left of one with right of other and vice versa.

2. Step 2: Trace the given trees

   tree1 has root 1, left 2, right 3; tree2 has root 1, left 3, right 2. They are mirrors, so isMirror returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Mirror check returns true for these trees [OK]

Hint: Mirror check compares opposite children recursively [OK]

Common Mistakes:

• Confusing left and right child comparison
• Assuming same structure means mirror
• Ignoring null checks

4. Identify the bug in this TypeScript function meant to check if two trees are symmetric:

function isSymmetric(t1: TreeNode | null, t2: TreeNode | null): boolean {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  if (t1.val !== t2.val) return false;
  return isSymmetric(t1.left, t2.left) && isSymmetric(t1.right, t2.right);
}

medium

A. It does not check node values before recursion.

B. It misses the base case when both nodes are null.

C. It returns true when one node is null and the other is not.

D. It compares left with left and right with right instead of mirror sides.

Solution

1. Step 1: Analyze recursive calls

   The function compares t1.left with t2.left and t1.right with t2.right, which checks identical structure, not mirror symmetry.

2. Step 2: Identify correct mirror comparison

   For symmetry, t1.left should be compared with t2.right and t1.right with t2.left.

3. Final Answer:

   It compares left with left and right with right instead of mirror sides. -> Option D

4. Quick Check:

   Mirror needs cross child comparison = A [OK]

Hint: Mirror check swaps left and right children in recursion [OK]

Common Mistakes:

• Comparing same side children instead of opposite
• Forgetting to check node values before recursion
• Missing null base cases

5. Given two binary trees, write a TypeScript function that returns true if they are symmetric around their roots, and false otherwise. Which approach correctly solves this problem?

hard

A. Use a helper function to recursively compare left subtree of one tree with right subtree of the other and vice versa.

B. Traverse both trees in preorder and compare the traversal arrays for equality.

C. Check if both trees have the same height and node count.

D. Compare only the root node values of both trees.

Solution

1. Step 1: Understand symmetry check requirements

   Symmetry means the left subtree of one tree is the mirror of the right subtree of the other.

2. Step 2: Choose correct approach

   Recursively comparing left subtree of one with right subtree of the other ensures mirror symmetry is checked properly.

3. Final Answer:

   Use a helper function to recursively compare left subtree of one tree with right subtree of the other and vice versa. -> Option A

4. Quick Check:

   Mirror recursion approach = B [OK]

Hint: Mirror symmetry needs cross subtree recursive comparison [OK]

Common Mistakes:

• Comparing preorder traversals which miss mirror structure
• Checking only height or node count
• Comparing only root values