Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

binary tree
symmetric

How to check for a symmetric binary tree (iterative approach)

Educative Answers Team

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.

svg viewer

Algorithm

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:

  1. If the tree is empty or consists of a single node, then it is symmetric.

  2. Enqueue the left and right child of the root node.

  3. 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:

1 of 10

Implementation

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

binary tree
symmetric
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring