Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

binary tree
symmetric

How to check for a symmetric binary tree (recursive 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​ an 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 steps are involved in the recursive approach:

  1. If the tree is empty, then it is symmetrical to the vertical axis going through its root node.

  2. Else, check if the value at the root node of both subtrees is the same.

  3. If it is, then check if the left subtree and the right subtree are symmetrical.

  4. This can be done by checking if:

    4.1 The root nodes of both trees contain the same value.

    4.2 The left subtree of the left subtree and the right subtree of the right subtree are symmetrical.

    4.3 The right subtree of the left subtree and the left subtree of the right subtree are symmetrical.

The following illustration shows the algorithm in action:

1 of 5

Implementation

The following code determines if a binary tree is symmetric or not, recursively​:

#include <iostream>
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; 
    }     
};
// Function to determine if a tree is symmetric. It returns
// true if the tree is symmetric and false otherwise.
bool SymmetricBt(Tree *root_s1, Tree *root_s2){
  // If the tree is empty, its symmetric
  if(!root_s1 && !root_s2){
    return true;
  }
  else{
    if(root_s1 && root_s2){
      // If the root nodes of the subtrees contain the same
      // value, recursively check if their subtrees are symmetric
      if(root_s1 -> data == root_s2 -> data){
        return SymmetricBt(root_s1 -> left, root_s2 -> right) &&
         SymmetricBt(root_s1 -> right, root_s2 -> left);
      }
    }
    return false;
  }
}
int main() {
  // 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');
  if (SymmetricBt(root, root)){
    cout<<"The binary tree is symmetric."<<endl;
  }
  else{
    cout<<"The binary tree is asymmetric."<<endl;
  }
  return 0;
}

RELATED TAGS

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

View all Courses

Keep Exploring