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

Concept Flow - Check if Two Trees are Symmetric

Start with root nodes of both trees

↓

Compare values of current nodes

↓

Return false - trees not symmetric

↓

Recursively check left of Tree1 with right of Tree2

↓

Recursively check right of Tree1 with left of Tree2

↓

Both recursive calls true?

Yes↓

Return true - trees are symmetric

Start by comparing root nodes, then recursively check if left subtree of one tree matches right subtree of the other, and vice versa, returning true only if all pairs match.

Execution Sample

DSA Javascript

function isSymmetric(t1, t2) {
  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 mirror images by comparing nodes recursively.

Execution Table

Step	t1 Node Value	t2 Node Value	Condition Checked	Result	Next Action
1	1	1	Both nodes exist and values equal?	true	Check left of t1 with right of t2 and right of t1 with left of t2
2	2	2	Both nodes exist and values equal?	true	Check left of t1.left with right of t2.right and right of t1.left with left of t2.right
3	3	3	Both nodes exist and values equal?	true	Check left and right children (both null)
4	null	null	Both nodes null?	true	Return true
5	null	null	Both nodes null?	true	Return true
6	null	null	Both nodes null?	true	Return true
7	null	null	Both nodes null?	true	Return true
8	2	2	Both nodes exist and values equal?	true	Check left of t1.right with right of t2.left and right of t1.right with left of t2.left
9	3	3	Both nodes exist and values equal?	true	Check left and right children (both null)
10	null	null	Both nodes null?	true	Return true
11	null	null	Both nodes null?	true	Return true
12	null	null	Both nodes null?	true	Return true
13	null	null	Both nodes null?	true	Return true
14	All recursive calls returned true			true	Return true - trees are symmetric

💡 All corresponding nodes matched or were both null, confirming symmetry.

Variable Tracker

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

Key Moments - 3 Insights

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

Because symmetry means one tree is a mirror image of the other, so left subtree of one matches right subtree of the other. See execution_table steps 1 and 2 where this cross comparison happens.

What happens when both nodes are null during recursion?

If both nodes are null, it means the branches ended symmetrically, so we return true. This is shown in execution_table steps 4, 5, 6, 7, 10, 11, 12, and 13.

Why do we return false immediately if one node is null and the other is not?

Because that means the structure is not symmetric at that point. The function returns false early to stop unnecessary checks, as seen in the condition checks in the code and implied in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what nodes are being compared?

A t1.left with t2.right

B t1.left with t2.left

C t1.right with t2.right

D t1.right with t2.left

💡 Hint

Check the 'Next Action' column in step 1 and the 't1 Node Value' and 't2 Node Value' columns in step 2.

At which step does the function confirm that both nodes are null and returns true?

A Step 3

B Step 4

C Step 8

D Step 14

💡 Hint

Look for rows where 'Condition Checked' is 'Both nodes null?' and 'Result' is true.

If at step 1 the root node values were different, what would be the result?

A Return true

B Return false

C Continue recursion

D Ignore and check children

💡 Hint

Refer to the 'Condition Checked' and 'Result' columns in step 1 of the execution_table.

Concept Snapshot

Check if Two Trees are Symmetric:
- Compare root nodes values.
- Recursively check t1.left with t2.right and t1.right with t2.left.
- If both nodes null, return true.
- If one null or values differ, return false.
- Return true only if all pairs match.

Full Transcript

This concept checks if two trees are mirror images. It starts by comparing the root nodes. If both are null, they are symmetric at that point. If one is null or values differ, they are not symmetric. Otherwise, it recursively compares 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. The process continues until all nodes are checked. If all pairs match, the trees are symmetric.

Practice

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

easy

A. They have the same root value only.

B. They have the same number of nodes.

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

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 C

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 structure differences

2. Which of the following is the correct JavaScript function signature to check if two trees are symmetric?

easy

A. function checkSymmetric(tree) {}

B. function isSymmetric(tree1, tree2) {}

C. function symmetricCheck(tree1, tree2, tree3) {}

D. function isSymmetric(tree1) {}

Solution

1. Step 1: Identify parameters needed

   To check symmetry between two trees, we need two tree inputs.

2. Step 2: Match function signature

   Only the function with two parameters for two trees matches the requirement.

3. Final Answer:

   function isSymmetric(tree1, tree2) {} -> Option B

4. Quick Check:

   Two trees need two parameters = B [OK]

Hint: Two trees need two parameters in function [OK]

Common Mistakes:

• Using only one tree parameter
• Adding unnecessary third parameter
• Wrong function naming

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

function isMirror(t1, t2) {
  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 = { val: 1, left: { val: 2, left: null, right: null }, right: { val: 3, left: null, right: null } };
const tree2 = { val: 1, left: { val: 3, left: null, right: null }, right: { val: 2, left: null, right: null } };

console.log(isMirror(tree1, tree2));

medium

A. TypeError

B. false

C. undefined

D. true

Solution

1. Step 1: Check base cases for null nodes

   Both trees have matching null nodes at corresponding mirror positions, so base cases return true.

2. Step 2: Compare node values and recursive calls

   Root values match (1), left of tree1 (2) matches right of tree2 (2), right of tree1 (3) matches left of tree2 (3). All recursive calls return true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Mirror check returns true for symmetric trees [OK]

Hint: Mirror check compares opposite children recursively [OK]

Common Mistakes:

• Confusing left and right children in recursion
• Ignoring null node base cases
• Assuming order of children doesn't matter

4. Identify the bug in this code snippet that checks if two trees are symmetric:

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

medium

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

B. It does not check for null nodes.

C. It uses assignment instead of comparison.

D. It returns true too early without recursion.

Solution

1. Step 1: Analyze recursive calls for symmetry

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

2. Step 2: Correct recursive calls for mirror check

   To check 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 A

4. Quick Check:

   Mirror check swaps sides in recursion = A [OK]

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

Common Mistakes:

• Comparing same sides instead of mirror sides
• Missing null checks
• Using assignment (=) instead of equality (===)

5. Given two binary trees, write a function to check if they are symmetric. Which approach correctly solves this problem?

hard

A. Use a queue to iteratively compare nodes from left of one tree and right of the other.

B. Compare only the root nodes of both trees.

C. Check if both trees have the same height only.

D. Traverse both trees in preorder and compare node values in order.

Solution

1. Step 1: Understand iterative symmetry check

   Using a queue, we can compare nodes from the left side of one tree with the right side of the other tree iteratively.

2. Step 2: Why other methods fail

   Preorder traversal compares nodes in the same order, not mirror order. Height check or root-only check ignores structure and values.

3. Final Answer:

   Use a queue to iteratively compare nodes from left of one tree and right of the other. -> Option A

4. Quick Check:

   Iterative mirror check uses queue swapping sides = D [OK]

Hint: Use queue to compare opposite sides iteratively [OK]

Common Mistakes:

• Using preorder traversal without mirroring
• Checking only height or root values
• Ignoring iterative approach benefits