Symmetric Trees in DAA
Symmetric Trees
The trees that are mirror images of themselves are known as symmetric trees.
Look at the following tree image below:
The tree is symmetric as the left subtree is the mirror image of the right subtree.
The below tree is not an example of the symmetric tree as the left child of the left subtree is not equal to the right child of the right subtree.
Let us now develop the algorithm to find whether the tree is symmetric or not. There are two methods recursive and iterative.
Method 1 (Iterative)
We need to identify if the left child of the left subtree is equal to the right child of the right subtree. For this check, we can take the help of queue data structure. Every time we will push each node in the queue and check for its equality. After that, we will pop it from the queue and push its left and right child if it exists and again compare for equality. The algorithm will traverse until we reach the leaf nodes.
Below is the implementation of method 1:
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Creating a binary tree
struct Node {
int key; // The value of the node
struct Node *left, *right; // The left and right pointers to the node
};
// Function to allocate memory to the new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL; // The child currently points to NULL
return (temp);
}
//The function will return true if the tree is symmetric. Else, false
bool isSymmetric(struct Node* root)
{
if (root == NULL) // If the tree has no node it is symmetric
return true;
// Case when exists only root node
if (!root->left && !root->right) // If the left and right are NULL
return true; // It is symmetric
queue<Node*> q; // Creating a queue
// We had pushed root two times in queue to check if there is only one child is alone or not
q.push(root);
q.push(root);
// Two nodes for checking the symmetry
Node *leftNode, *rightNode;
while (!q.empty()) { // Iterate in the queue
// Remove the first two nodes to check symmetry
leftNode = q.front(); // Taking that node
q.pop(); // popping it from queue
// The second node
rightNode = q.front();
q.pop();
// Return false if the values are not same of leftNode and rightNode
if (leftNode->key != rightNode->key) { /// Keys are not similar
return false; // Not symmertic
}
// If the current nnode has children ie not null
if (leftNode->left && rightNode->right) {
q.push(leftNode->left); // push left child in queue
q.push(rightNode->right); // push right child in queue
}
// if any one child is missing return false
else if (leftNode->left || rightNode->right)
return false;
if (leftNode->right && rightNode->left) { // If both parent node exists
q.push(leftNode->right); // push the right child in the queue
q.push(rightNode->left); //push the left child in the queue
}
// Case of single child of a parent exists
else if (leftNode->right || rightNode->left)
return false;
}
return true;
}
// Main function
int main()
{
// Construct the symmetric tree
Node* root = newNode(1); // Root node
root->left = newNode(2); // left of root
root->right = newNode(2); // right of root
root->left->left = newNode(3); // left child of 2
root->left->right = newNode(4); // right child of 2
root->right->left = newNode(4); // left child of parent right 2
root->right->right = newNode(3); // right child of parent right 2
if (isSymmetric(root)) // call function isSymmetric
cout << "The tree is Symmetric";
else
cout << "The tree is not Symmetric";
return 0;
}
Output:
The given tree is Symmetric
Method 2 (Recursive)
This method takes a left and right of a level and checks at each stage if the left child is equal to the right child until it reaches the leaf nodes.
The below code shows recursive approach:
C++ code:
#include <bits/stdc++.h>
using namespace std;
// Creating a binary tree
struct Node {
int key; // The value of the node
struct Node *left, *right; // The left and right pointers to the node
};
// Function to allocate memory to the new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key; // Store the tree node value
temp->left = temp->right = NULL; // The child currently points to NULL
return (temp); // return current pointer of tree
}
// Passed two trees with roots as root1 and root2
bool isMirror(struct Node* root1, struct Node* root2)
{
if (root1 == NULL && root2 == NULL) // If both of them are NULL
return true; // return true for being mirror images
// If both root values exist and both root have equal root values
// check for the left - right subtree and right - left subtree
if (root1 && root2 && root1->key == root2->key)
return isMirror(root1->left, root2->right)
&& isMirror(root1->right, root2->left); // It will call recursively
return false; // If both conditions are not satisfied
}
// The function gives true if symmetric else non symmetric return false
bool isSymmetric(struct Node* root)
{
// The isMirror is a recursive function that sends root and root to check the
// symmetric tree existence
return isMirror(root, root);
}
// Main function
int main()
{
// Construct the symmetric tree
Node* root = newNode(1); // Root node
root->left = newNode(2); // left of root
root->right = newNode(2); // right of root
root->left->left = newNode(3); // left child of 2
root->left->right = newNode(4); // right child of 2
root->right->left = newNode(4); // left child of parent right 2
root->right->right = newNode(3); // right child of parent right 2
if (isSymmetric(root)) // call function isSymmetric
cout << "The tree is Symmetric";
else
cout << "The tree is not Symmetric";
return 0; // return from main
}
Output:
The tree is Symmetric