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 treeTree *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;}
Free Resources