Check whether 2 Binary trees are identical or not

March 24, 2025

Check for identical binary trees

A binary tree is said to be identical with another binary tree if both the trees have the same data and also the same arrangement of the data.In this article, we will learn the approach and code to check whether 2 binary trees are identical or not.

Check whether 2 binary trees are identical or not
What are identical Trees?

Given root nodes of 2 trees and we need to find that whether the trees are identical or not.
Trees being identical means that they are same in terms of structures, same in terms of the number of nodes and also same in terms of links.

Eg:- (Insert Image)

For the above Input, the value returned by the method  for trees 1 and 2 should be true as both the trees are identical.

Trees 1 and 2 are identical to each other whereas 2 and 3  are not.

Approach:-

Inorder to compare  two trees we can traverse the trees , store their traversal sequences in an array and then match two arrays .

However, this approach might not always be right. There might be an exception to the case wherever the traversal leads the same result but trees are not identical.
This is left as an exercise to the reader to think of an example where trees have traversal sequence same but aren’t identical.

Find the size of binary tree

Find maximum in binary tree

Spiral Order traversal of Tree

Level Order Traversal LIne by Line

Check If binary tree if Foldable or not

Code Implementation to check whether two binary trees are identical or not in C++

Run 
#include<bits/stdc++.h>
struct node			
{
  int val;
  struct node *lchild;
  struct node *rchild;
};

struct node *newNode (int key)		
{
  struct node *newnode = (struct node *) malloc (sizeof (struct node));
  newnode->val = key;
  newnode->lchild = NULL;
  newnode->rchild = NULL;

  return (newnode);
}

int areidentical (struct node *node1, struct node *node2)
{

  if (node1 == NULL && node2 == NULL)
    return 1;

  if (node1 != NULL && node2 != NULL)
    {
      return (node1->val == node2->val
	      && areidentical (node1->lchild, node2->lchild)
	      && areidentical (node1->rchild, node2->rchild));
    }

  else
    return 0;
}

int main ()
{
  struct node *root1 = newNode (232);
  struct node *root2 = newNode (232);
  root1->lchild = newNode (231);
  root1->rchild = newNode (231);
  root1->lchild->lchild = newNode (431);
  root1->lchild->rchild = newNode (531);

  root2->lchild = newNode (231);
  root2->rchild = newNode (331);
  root2->lchild->lchild = newNode (431);
  root2->lchild->rchild = newNode (513);

  if (areidentical (root1, root2))
    printf ("Both tree are identical.");
  else
    printf ("Trees are not identical.");

  getchar ();
  return 0;
}

Output:
Trees are not identical.