A binary tree is symmetric if itâ€™sâ€‹ left and right subtrees are identical mirror images of each other. The following illustrations show a symmetric and asymmetric binary tree.
In order to determine if a binary tree is symmetric or not, a recursive or iterative approach can be used. The following are the steps involved in the iterative approach:
If the tree is empty or consists of a single node, then it is symmetric.
Enqueue the left and right child of the root node.
While the queue is not empty:
3.1 Remove the first two elements from the queue; letâ€™s call them Left
and Right
.
3.2 Check if node Left
has a left child, and node Right
has a corresponding right child (and vice versa). If it does not, then the tree is asymmetric.
3.3 Check if node Left
has a right child, and node Right
has a corresponding left child (and vice versa). If it does not, then the tree is asymmetric.
3.4 Câ€‹heck if the elements have the same value. If they do not, then the tree is asymmetric.
3.5 Enqueue the left child of node Left
, and the right child of node Right
if both of them exist.
3.6 Eâ€‹nqueue the right child of node Left
and the left child of node Right
if both of them exist.
The following illustration shows the algorithm in action:
The following code determines if a binary tree is symmetric or not, iteratively:
#include <iostream> #include <queue> using namespace std; // Creating a tree node. struct Tree { char data; Tree *left; Tree *right; Tree(char data) { this -> data = data; left = NULL; right = NULL; } }; int main() { // Flag = 0 denotes that a tree is symmetric. int flag = 0; // Creating a tree Tree *root = new Tree('1'); root -> left = new Tree('3'); root -> right = new Tree('3'); root -> left -> left = new Tree('4'); root -> left -> right = new Tree('6'); root -> right -> left = new Tree('6'); root -> right -> right = new Tree('4'); // Creating a queue that will hold pointers to the tree nodes. queue<Tree*> Q; // Notice that if the tree is empty or contains only one node // then it is symmetric. if(root != NULL || (root -> left == NULL && root -> right == NULL)){ Q.push(root); Q.push(root); while(!Q.empty()){ // Seeing and removing the top two elements of the queue. Tree *Left = Q.front(); Q.pop(); Tree *Right = Q.front(); Q.pop(); if (Left -> left == NULL && Right -> right != NULL){ cout<<"The binary tree is asymmetric"<<endl; // Setting flag to -1 if it is asymmetric. flag = -1; break; } if (Left -> left != NULL && Right -> right == NULL){ cout<<"The binary tree is asymmetric"<<endl; // Setting flag to -1 if it is asymmetric. flag = -1; break; } if (Left -> right != NULL && Right -> left == NULL){ cout<<"The binary tree is asymmetric"<<endl; // Setting flag to -1 if it is asymmetric. flag = -1; break; } if (Left -> right == NULL && Right -> left != NULL){ cout<<"The binary tree is asymmetric"<<endl; // Setting flag to -1 if it is asymmetric. flag = -1; break; } if(Left -> data != Right -> data){ cout<<"The binary tree is asymmetric"<<endl; // Setting flag to -1 if it is asymmetric. flag = -1; break; } if(Left -> left != NULL && Right -> right != NULL){ Q.push(Left -> left); Q.push(Right -> right); } if(Left -> right != NULL && Right -> left != NULL){ Q.push(Left -> right); Q.push(Right -> left); } } } if(flag == 0){ cout<<"The binary tree is symmetric"<<endl; } return 0; }
RELATED TAGS
View all Courses