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

🎯 Goal: Build a program that creates two binary trees, sets up a helper function to check symmetry, and then uses this function to determine if the two trees are symmetric.

📋 What You'll Learn

Create two binary trees with exact node values

Create a helper function called isMirror that checks if two trees are mirror images

Create a function called areSymmetric that uses isMirror to check symmetry

Print true if the trees are symmetric, otherwise false

💡 Why This Matters

🌍 Real World

Checking if two trees are symmetric is useful in graphics, data validation, and comparing hierarchical data structures.

💼 Career

Understanding tree symmetry helps in coding interviews and software roles involving tree data structures and recursion.

1

Create Two Binary Trees

Create a struct called Node with an int data, and two pointers left and right. Then create two binary trees called tree1 and tree2 with these exact nodes and structure:

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

DSA C++

// Define struct Node
// Create tree1 and tree2 with given nodes
// Your code here

Hint

Define the Node struct first. Then create tree1 and tree2 by assigning new nodes with the exact values and structure.

2

Create Helper Function isMirror

Create a function called isMirror that takes two Node* parameters named root1 and root2. This function should return true if the two trees are mirror images of each other, and false otherwise. Use these rules:
- If both nodes are nullptr, return true
- If one is nullptr and the other is not, return false
- Check if root1->data equals root2->data and recursively check root1->left with root2->right and root1->right with root2->left

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* tree1 = new Node(1);
tree1->left = new Node(2);
tree1->right = new Node(3);

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

// Create isMirror function below
// Your code here

Hint

Use recursion to compare the nodes and their children in mirror order.

3

Create Function areSymmetric

Create a function called areSymmetric that takes two Node* parameters named root1 and root2. This function should return the result of calling isMirror(root1, root2).

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* tree1 = new Node(1);
tree1->left = new Node(2);
tree1->right = new Node(3);

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

bool isMirror(Node* root1, Node* root2) {
    if (root1 == nullptr && root2 == nullptr) return true;
    if (root1 == nullptr || root2 == nullptr) return false;
    return (root1->data == root2->data) &&
           isMirror(root1->left, root2->right) &&
           isMirror(root1->right, root2->left);
}

// Create areSymmetric function below
// Your code here

Hint

This function just calls isMirror with the two roots.

4

Print if Trees are Symmetric

Use std::cout to print true if areSymmetric(tree1, tree2) returns true, otherwise print false.

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* tree1 = new Node(1);
tree1->left = new Node(2);
tree1->right = new Node(3);

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

bool isMirror(Node* root1, Node* root2) {
    if (root1 == nullptr && root2 == nullptr) return true;
    if (root1 == nullptr || root2 == nullptr) return false;
    return (root1->data == root2->data) &&
           isMirror(root1->left, root2->right) &&
           isMirror(root1->right, root2->left);
}

bool areSymmetric(Node* root1, Node* root2) {
    return isMirror(root1, root2);
}

// Print the result below
// Your code here

Hint

Use std::cout and the ternary operator to print true or false based on the result of areSymmetric(tree1, tree2).