Check if Two Trees are Symmetric in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for two trees to be symmetric?

Two trees are symmetric if one is a mirror reflection of the other. This means the left subtree of one tree matches the right subtree of the other, and vice versa.

beginner

What is the base case when checking if two trees are symmetric?

If both trees are empty (null), they are symmetric. If only one is empty, they are not symmetric.

intermediate

How do you compare nodes when checking tree symmetry?

Compare the values of the current nodes. Then recursively check if the left child of one tree is symmetric with the right child of the other tree, and vice versa.

intermediate

Why is recursion useful for checking tree symmetry?

Recursion naturally explores both trees at the same time, comparing corresponding nodes and their children in a mirrored way, making the code simple and clear.

intermediate

What is the time complexity of checking if two trees are symmetric?

The time complexity is O(n), where n is the number of nodes in the trees, because each node is visited once during the comparison.

What should you check first when comparing two trees for symmetry?

A If the root values are different

B If the left child of both nodes are equal

C If the right child of both nodes are equal

D If both nodes are null

If both nodes are null, they are symmetric at this point. This is the base case for recursion.

When checking symmetry, which pairs of nodes do you compare recursively?

A Left child of first tree with right child of second tree

B Right child of first tree with right child of second tree

C Left child of first tree with left child of second tree

D Root nodes only

Symmetry means the left subtree of one tree matches the right subtree of the other, so compare left child of one with right child of the other.

If one node is null and the other is not, what does that mean for symmetry?

A Trees are symmetric

B Trees are not symmetric

C Check children nodes

D Ignore null nodes

If one node is null and the other is not, the trees differ in structure and are not symmetric.

What is the main idea behind the recursive function to check symmetry?

A Compare nodes in mirrored positions

B Compare nodes in the same position

C Count nodes in both trees

D Check if trees have the same height

The function compares nodes in mirrored positions to verify symmetry.

What happens if the root values of the two trees are different?

A Check children nodes

B Trees are symmetric

C Trees are not symmetric

D Ignore root values

If root values differ, trees cannot be symmetric.

Explain how to check if two trees are symmetric using recursion.

Think about mirror positions and base cases.

Describe the time complexity and why it is that way when checking tree symmetry.

Consider how many nodes you compare.

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