/
Symmetric_Tree.cpp
90 lines (88 loc) · 2.19 KB
/
Symmetric_Tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*Name : Atul Kumar
Github username : atul1510
Repositary name : Algorithms
Problem Description:
Given a binary tree, check whether it is a mirror of itself.
Examples:
1] INPUT:
1
/
2 2
/ \ /
3 4 4 3
OUTPUT: Symmetric
2] INPUT:
1
/
2 2
\
3 3
OUTPUT: Not symmetric */
// C++ program to check if a given Binary Tree is symmetric or not
#include <iostream>
using namespace std;
// Construct a Binary Tree Node
struct Node
{
int key;
struct Node* left, *right;
};
// function to create a new Node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Returns true if trees with roots as childL and childR are mirror image of each other
bool isSymmetric(struct Node* root1, struct Node* root2)
{
// If both trees are empty, then they are mirror images
if (root1 == NULL && root2 == NULL)
return true;
// For two trees to be mirror images, the following 3 conditions must be true
// a) Their root node's key must be same
// b) left subtree of left tree and right subtree of right tree have to be mirror images
// c) right subtree of left tree and left subtree of right tree have to be mirror images
if (root1 && root2 && root1->key == root2->key)
return isSymmetric(root1->left, root2->right)
&& isSymmetric(root1->right, root2->left);
// if none of above conditions is true then childL and childR are not mirror images
return false;
}
// Returns true if a tree is symmetric.
bool isSimilar(struct Node* root)
{
// Check if tree is mirror of itself
return isSymmetric(root, root);
}
// Function to take input from user
Node* takeInput()
{
int val;
cout << "Enter root value (-1 for no node): ";
cin >> val;
if (val == -1) {
return NULL;
}
Node* root = newNode(val);
root->left = takeInput();
root->right = takeInput();
return root;
}
// Main function
int main()
{
// Take input for the binary tree
cout << "Enter elements of the binary tree:\n";
Node* root = takeInput();
if (isSimilar(root))
{
cout << "The tree is symmetric";
}
else {
cout << "The tree is not symmetric";
}
return 0;
}