ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Check if two binary tree are identical

prodevelopertutorial March 30, 2020

In this chapter, we shall see if 2 trees are identical.

 

Problem statement:

You are given root node of 2 binary trees, you need to check if 2 trees are identical.

 

Example:

 

Consider the below image

Check if 2 binary tree are identical

 

The first set are identical; the second set are not identical.

 

From the image we can derive below true cases:

 

  1. If both nodes are null, then return true
  2. If the right node value of tree 1 is equal to the right node value of tree 2, return true.
  3. If the Left node value of tree 1 is equal to the Left node value of tree 2, return true.

 

From the image we can derive below false cases:

  1. If a node from tree 1 has value, and node from tree 2 is null, then return false.
  2. If both the tree nodes have a value, but they are different, then return false.

Solution in C++

#include <iostream>
#include <stack>
#include <map>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

int check_is_identical(Node* root1, Node* root2) 
{ 
    if (root1 == NULL && root2 == NULL) 
        return 1; 

    else if (root1 != NULL && root2 == NULL) 
        return 0; 
    else if (root1 == NULL && root2 != NULL) 
        return 0; 
    else { 
        if (root1->data == root2->data && check_is_identical(root1->left, root2->left) 
            && check_is_identical(root1->right, root2->right)) 
            return 1; 
        else
            return 0; 
    } 
} 
  
  
  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    Node* root_1 = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          25      10
         /  \    /  \
        /    \  /    \
       30    18 15     7

    */

    root_1 = new Node(16);
    root_1->left = new Node(25);
    root_1->right = new Node(10);
    root_1->left->left = new Node(30);
    root_1->left->right = new Node(18);
    root_1->right->left = new Node(15);
    root_1->right->right = new Node(7);

    if(check_is_identical(root, root_1))
    {
        cout<<"Both of them are identical"<<endl;
    } else {
        cout<<"Both of them are not identical"<<endl;
    }

    return 0;  
}

 

Output:

Both of them are not identical

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io