Check if Two Trees are Symmetric in DSA C - Build from Scratch

Check if Two Trees are Symmetric

📖 Scenario: Imagine you have two family trees represented as binary trees. You want to check if these two trees are mirror images of each other, meaning they are symmetric in structure and values.

🎯 Goal: Build a program that creates two binary trees, sets up a helper function to check symmetry, implements the logic to verify if the two trees are symmetric, and finally prints the result.

📋 What You'll Learn

Create two binary trees with exact node values

Add a helper function pointer or variable for symmetry checking

Implement a function to check if two trees are symmetric

Print "Symmetric" if trees are symmetric, else "Not Symmetric"

💡 Why This Matters

🌍 Real World

Checking if two trees are symmetric is useful in comparing hierarchical data structures like organizational charts or XML/JSON data.

💼 Career

Understanding tree symmetry helps in software development roles involving data structure manipulation, algorithms, and system design.

1

Create two binary trees

Create two binary trees called tree1 and tree2 with the following structure and values:

tree1: root node value 1, left child 2, right child 3
tree2: root node value 1, left child 3, right child 2

Use the struct Node definition provided.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Create tree1
    // Your code here

Hint

Use the newNode function to create nodes and assign them to tree1 and tree2 with the exact values.

2

Add a helper function declaration

Declare a function called isSymmetricHelper that takes two parameters of type struct Node* and returns an int. This function will be used to check if two trees are symmetric.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Declare the helper function
// Your code here

int main() {
    struct Node* tree1 = newNode(1);
    tree1->left = newNode(2);
    tree1->right = newNode(3);

    struct Node* tree2 = newNode(1);
    tree2->left = newNode(3);
    tree2->right = newNode(2);

    return 0;
}

Hint

Write the function declaration with the exact name isSymmetricHelper and parameters struct Node* root1, struct Node* root2.

3

Implement the symmetry check function

Implement the function isSymmetricHelper that returns 1 if two trees are symmetric and 0 otherwise. Use the following logic:
- If both nodes are NULL, return 1
- If one node is NULL and the other is not, return 0
- If the data in both nodes is equal, recursively check if left subtree of first tree is symmetric with right subtree of second tree and right subtree of first tree is symmetric with left subtree of second tree
- Otherwise, return 0

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Implement the helper function
int isSymmetricHelper(struct Node* root1, struct Node* root2) {
    // Your code here
}

int main() {
    struct Node* tree1 = newNode(1);
    tree1->left = newNode(2);
    tree1->right = newNode(3);

    struct Node* tree2 = newNode(1);
    tree2->left = newNode(3);
    tree2->right = newNode(2);

    return 0;
}

Hint

Follow the logic step by step using if statements and recursive calls as described.

4

Print if the two trees are symmetric

In the main function, call isSymmetricHelper(tree1, tree2). If it returns 1, print "Symmetric". Otherwise, print "Not Symmetric".

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Implement the helper function
int isSymmetricHelper(struct Node* root1, struct Node* root2) {
    if (root1 == NULL && root2 == NULL) {
        return 1;
    }
    if (root1 == NULL || root2 == NULL) {
        return 0;
    }
    if (root1->data != root2->data) {
        return 0;
    }
    return isSymmetricHelper(root1->left, root2->right) && isSymmetricHelper(root1->right, root2->left);
}

int main() {
    struct Node* tree1 = newNode(1);
    tree1->left = newNode(2);
    tree1->right = newNode(3);

    struct Node* tree2 = newNode(1);
    tree2->left = newNode(3);
    tree2->right = newNode(2);

    // Print if symmetric
    // Your code here

    return 0;
}

Hint

Use an if statement to check the return value of isSymmetricHelper(tree1, tree2) and print the exact strings "Symmetric" or "Not Symmetric".

Practice

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

easy

A. They are mirror images of each other around their roots

B. They have the same number of nodes

C. They have the same preorder traversal

D. They have the same height

Solution

1. Step 1: Understand symmetry in trees

   Two trees are symmetric if one is the mirror reflection of the other around their roots.

2. Step 2: Compare with other options

   Having the same number of nodes, preorder traversal, or height does not guarantee mirror symmetry.

3. Final Answer:

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

4. Quick Check:

   Symmetry means mirror image = A [OK]

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

Common Mistakes:

• Confusing same size with symmetry
• Thinking same traversal means symmetric
• Assuming same height means symmetric

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

easy

A. int isSymmetric(struct Node* root1, struct Node* root2);

B. void isSymmetric(struct Node root1, struct Node root2);

C. int isSymmetric(struct Node root1, struct Node root2);

D. int isSymmetric(Node* root1, Node root2);

Solution

1. Step 1: Understand pointer usage in C for trees

   Tree nodes are accessed via pointers, so parameters must be pointers to struct Node.

2. Step 2: Analyze each option

   int isSymmetric(struct Node* root1, struct Node* root2); uses pointers correctly and returns int for boolean result. Options A and B pass structs by value, which is inefficient and incorrect. int isSymmetric(Node* root1, Node root2); mixes pointer and non-pointer types incorrectly.

3. Final Answer:

   int isSymmetric(struct Node* root1, struct Node* root2); -> Option A

4. Quick Check:

   Use pointers for tree nodes in C function [OK]

Hint: Use pointers to struct Node for tree parameters [OK]

Common Mistakes:

• Passing structs by value instead of pointers
• Mixing pointer and non-pointer parameters
• Using void return type instead of int for boolean

3. What will be the output of the following code snippet checking symmetry of two trees?

struct Node {
  int val;
  struct Node* left;
  struct Node* right;
};

int isMirror(struct Node* t1, struct Node* t2) {
  if (!t1 && !t2) return 1;
  if (!t1 || !t2) return 0;
  return (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left);
}

int main() {
  struct Node n1 = {1, NULL, NULL};
  struct Node n2 = {1, NULL, NULL};
  printf("%d", isMirror(&n1, &n2));
  return 0;
}

medium

A. 0

B. 1

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze base cases and node values

   Both nodes have value 1 and no children, so both left and right pointers are NULL.

2. Step 2: Evaluate recursive calls

   isMirror returns 1 if both nodes are NULL (true). Since both left and right children are NULL, recursive calls return 1. Values match, so overall returns 1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Identical single nodes are symmetric = 1 [OK]

Hint: Single nodes with same value are symmetric [OK]

Common Mistakes:

• Confusing NULL children as asymmetric
• Expecting 0 for identical nodes
• Misreading recursive base cases

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

int isMirror(struct Node* t1, struct Node* t2) {
  if (t1 == NULL && t2 == NULL) return 1;
  if (t1 == NULL || t2 == NULL) return 0;
  if (t1->val != t2->val) return 0;
  return isMirror(t1->left, t2->left) && isMirror(t1->right, t2->right);
}

medium

A. Should use OR instead of AND in return statement

B. Missing check for NULL nodes

C. Return type should be void

D. Should compare t1->left with t2->right and t1->right with t2->left

Solution

1. Step 1: Understand mirror symmetry check

   Mirror symmetry requires left subtree of one tree to match right subtree of the other and vice versa.

2. Step 2: Identify incorrect recursive calls

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

3. Final Answer:

   Should compare t1->left with t2->right and t1->right with t2->left -> Option D

4. Quick Check:

   Mirror means cross compare left and right subtrees [OK]

Hint: Mirror check swaps left and right subtrees [OK]

Common Mistakes:

• Comparing left with left and right with right
• Ignoring NULL checks
• Using wrong logical operators

5. Given two binary trees, how would you implement a function to check if they are symmetric using a queue (iterative approach)? Which step is essential in this approach?

hard

A. Compare only root nodes and ignore children

B. Traverse both trees in preorder and compare arrays

C. Enqueue pairs of nodes to compare left of one with right of other

D. Use a stack to store nodes from only one tree

Solution

1. Step 1: Understand iterative symmetry check

   Use a queue to store pairs of nodes to compare their values and subtrees iteratively.

2. Step 2: Identify correct node pairing

   Pairs must be left child of one tree with right child of the other to check mirror symmetry.

3. Step 3: Reject incorrect approaches

   Preorder traversal comparison or using stack for one tree only does not check mirror symmetry. Ignoring children misses the point.

4. Final Answer:

   Enqueue pairs of nodes to compare left of one with right of other -> Option C

5. Quick Check:

   Queue pairs left-right nodes for iterative mirror check [OK]

Hint: Queue pairs left and right nodes to check symmetry iteratively [OK]

Common Mistakes:

• Comparing same side children instead of opposite
• Using preorder traversal arrays
• Ignoring children nodes in comparison