Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Prerequisites
1.2.
Problem Statement
1.3.
Sample Example
2.
Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a Tree?
3.2.
What is a Binary Tree?
3.3.
What is a subtree?
4.
Conclusion
Last Updated: Mar 27, 2024

Check if Two Binary Trees are Identical

Author Anju Jaiswal
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

In this blog we will discuss the problem, i.e., " Check if Two Binary Trees are Identical,". It is highly asked in product-based companies. We'll go over all the steps of the solution.

Let's get started with the problem statement without further ado.

Prerequisites

Knowledge of trees and related terminologies such as recursiontrees, and the main traversals inorderpreorderpostorder are common prerequisites for every tree problem. It is not advisable to proceed to Check if Two Binary Trees are Identical in trees without mastering these fundamental methods and data structures.

Nonetheless, we'll try to go through every detail needed to Check if Two Binary Trees are Identical.

Problem Statement

Write an efficient algorithm to Check if Two Binary Trees are Identical. If two binary trees contain identical structures and data, they are said to be identical.

To determine whether two trees are identical, we must traverse both trees simultaneously and compare the data and children of the trees.

Sample Example

Input:

                        

Output: True

Explanation:  The structure and contents of both binary trees are identical.

Approach

To determine whether two trees are the same, we must walk both trees simultaneously and compare their data and children.

Pseudocode

Check if Two Binary Trees are Identical (Binary Tree 1, Binary Tree 2)

1.  If both binary trees are empty, then return TRUE.

2. Else If both binary trees are non-empty

     (a)  Check data of the root nodes (root node root Binary Tree 1->data == root node of Binary Tree 2->data)

     (b) Check left subtrees recursively, i.e., Check if Two Binary Trees are Identical(

          Binary Tree 1->left_subtree, Binary Tree 2->left_subtree)
 

 

     (c) Check right subtrees recursively, i.e., Check if Two Binary Trees are Identical(

          Binary Tree 1->right_subtree, Binary Tree 2->right_subtree)

     (d) If a,b and c are true then return TRUE.

3 Else return FALSE (one is empty, and the other is not)

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

class node {
  public:
    int data;
  node * left;
  node * right;
};

node * newNode(int data) {
  node * Node = new node();
  Node -> data = data;
  Node -> left = NULL;
  Node -> right = NULL;

  return (Node);
}

/* Function to Check if Two Binary Trees are Identical */
bool Check_if_Two_Binary_Trees_are_Identical(node * root1, node * root2) {
  /* if both binary trees are empty then return TRUE. */

  if (root1 == NULL && root2 == NULL)
    return true;

  if (root1 != NULL && root2 != NULL) {

    /*Check data of the root nodes */
    bool a = root1 -> data == root2 -> data;

    /*Check left subtrees recursively*/

    bool b = Check_if_Two_Binary_Trees_are_Identical(root1 -> left, root2 -> left);

    /*Check right subtrees recursively*/

    bool c = Check_if_Two_Binary_Trees_are_Identical(root1 -> right, root2 -> right);
    return a && b && c;

  }

  return false;
}

/* Driver code*/
int main() {
  cout << "Check if Two Binary Trees are Identical : ";

  /*Binary tree 1*/
  node * root1 = newNode(6);
  root1 -> left = newNode(5);
  root1 -> right = newNode(9);
  root1 -> left -> left = newNode(12);
  root1 -> left -> right = newNode(3);
  root1 -> right -> left = newNode(7);
  root1 -> right -> right = newNode(6);

  /*Binary tree 2*/
  node * root2 = newNode(6);
  root2 -> left = newNode(5);
  root2 -> right = newNode(9);
  root2 -> left -> left = newNode(12);
  root2 -> left -> right = newNode(3);
  root2 -> right -> left = newNode(7);
  root2 -> right -> right = newNode(6);

  if (Check_if_Two_Binary_Trees_are_Identical(root1, root2))
    cout << "Both trees are identical.";
  else
    cout << "Trees are not identical.";

  return 0;
}

 

Output:

Check if Two Binary Trees are Identical : Both trees are identical.

 

Complexity Analysis

Time complexity: O(n)

According to the tree with a lesser number of nodes. Let the number of nodes in two trees be m and n; then complexity will be O(m) where m <n.

Space complexity: O(1)

No extra space is used.

Check out this problem - Duplicate Subtree In Binary Tree

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a Tree?

A tree is a type of hierarchical data structure that is made up of nodes. Value is represented by nodes, which are connected by edges. The following are the characteristics of a tree: The root node is the only node in the tree. This is where the tree comes from, so it has no parents.

What is a Binary Tree?

Each node can have a maximum of two children in a binary tree. Because the binary designation implies 'two,' each node can have either zero, one, or two children.

What is a subtree?

Any node in a tree and the descendants of that node.

Conclusion

This article discussed how to Check if Two Binary Trees are identical, with examples and their C++ code.

 

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Live masterclass