Open In App

Program to Determine if given Two Trees are Identical or not

Last Updated : 21 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Write a function to determine if two trees are identical or not:

Two trees are identical when they have the same data and the arrangement of data is also the same

Examples:

Input:         1                    1
                 /   \                /   \
               2      3            2      3
             /                    /
           4                   4

Output: Both trees are identical

Input:         1                    1
                 /   \                /   \
               2      3            5      3
                     /             /
                  4             4

Output: Trees are not identical

Approach: To solve the problem follow the below idea:

To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees

Follow the given steps to solve the problem:

  • If both trees are empty then return 1(Base case)
  • Else If both trees are non-empty
    • Check data of the root nodes (tree1->data ==  tree2->data)
    • Check left subtrees recursively
    • Check right subtrees recursively
    • If the above three statements are true then return 1
  • Else return 0 (one is empty and the other is not)

Below is the implementation of this approach:

C++ 
// C++ program to see if two trees are identical
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;

    return (Node);
}

/* Given two trees, return true if they are
structurally identical */
int identicalTrees(node* a, node* b)
{
    /*1. both empty */
    if (a == NULL && b == NULL)
        return 1;

    /* 2. both non-empty -> compare them */
    if (a != NULL && b != NULL) {
        return (a->data == b->data
                && identicalTrees(a->left, b->left)
                && identicalTrees(a->right, b->right));
    }

    /* 3. one empty, one not -> false */
    return 0;
}

/* Driver code*/
int main()
{
    node* root1 = newNode(1);
    node* root2 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);
    root1->left->left = newNode(4);
    root1->left->right = newNode(5);

    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);

      // Function call
    if (identicalTrees(root1, root2))
        cout << "Both trees are identical.";
    else
        cout << "Trees are not identical.";

    return 0;
}

// This code is contributed by rathbhupendra
C 
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return (node);
}

/* Given two trees, return true if they are
 structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
    /*1. both empty */
    if (a == NULL && b == NULL)
        return 1;

    /* 2. both non-empty -> compare them */
    if (a != NULL && b != NULL) {
        return (a->data == b->data
                && identicalTrees(a->left, b->left)
                && identicalTrees(a->right, b->right));
    }

    /* 3. one empty, one not -> false */
    return 0;
}

/* Driver code*/
int main()
{
    struct node* root1 = newNode(1);
    struct node* root2 = newNode(1);
    root1->left = newNode(2);
    root1->right = newNode(3);
    root1->left->left = newNode(4);
    root1->left->right = newNode(5);

    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);

      // Function call
    if (identicalTrees(root1, root2))
        printf("Both tree are identical.");
    else
        printf("Trees are not identical.");

    getchar();
    return 0;
}
Java 
// Java program to see if two trees are identical

// A binary tree node
class Node {
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }
}

class BinaryTree {
    Node root1, root2;

    /* Given two trees, return true if they are
       structurally identical */
    boolean identicalTrees(Node a, Node b)
    {
        /*1. both empty */
        if (a == null && b == null)
            return true;

        /* 2. both non-empty -> compare them */
        if (a != null && b != null)
            return (a.data == b.data
                    && identicalTrees(a.left, b.left)
                    && identicalTrees(a.right, b.right));

        /* 3. one empty, one not -> false */
        return false;
    }

    /* Driver code*/
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();

        tree.root1 = new Node(1);
        tree.root1.left = new Node(2);
        tree.root1.right = new Node(3);
        tree.root1.left.left = new Node(4);
        tree.root1.left.right = new Node(5);

        tree.root2 = new Node(1);
        tree.root2.left = new Node(2);
        tree.root2.right = new Node(3);
        tree.root2.left.left = new Node(4);
        tree.root2.left.right = new Node(5);

          // Function call
        if (tree.identicalTrees(tree.root1, tree.root2))
            System.out.println("Both trees are identical");
        else
            System.out.println("Trees are not identical");
    }
}
Python 
# Python3 program to determine if two trees are identical

# A binary tree node has data, pointer to left child
# and a pointer to right child


class Node:
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


# Given two trees, return true if they are structurally
# identical
def identicalTrees(a, b):

    # 1. Both empty
    if a is None and b is None:
        return True

    # 2. Both non-empty -> Compare them
    if a is not None and b is not None:
        return ((a.data == b.data) and
                identicalTrees(a.left, b.left)and
                identicalTrees(a.right, b.right))

    # 3. one empty, one not -- false
    return False


# Driver code
root1 = Node(1)
root2 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)

root2.left = Node(2)
root2.right = Node(3)
root2.left.left = Node(4)
root2.left.right = Node(5)

# Function call
if __name__ == "__main__":
  if identicalTrees(root1, root2):
      print("Both trees are identical")
  else:
      print("Trees are not identical")

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C# 
// C# program to see if two trees are identical
using System;

// C# program to see if two trees are identical

// A binary tree node
public class Node {
    public int data;
    public Node left, right;

    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    public Node root1, root2;

    /* Given two trees, return true if they are
       structurally identical */
    public virtual bool identicalTrees(Node a, Node b)
    {
        /*1. both empty */
        if (a == null && b == null) {
            return true;
        }

        /* 2. both non-empty -> compare them */
        if (a != null && b != null) {
            return (a.data == b.data
                    && identicalTrees(a.left, b.left)
                    && identicalTrees(a.right, b.right));
        }

        /* 3. one empty, one not -> false */
        return false;
    }

    /* Driver program to test identicalTrees() function */
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();

        tree.root1 = new Node(1);
        tree.root1.left = new Node(2);
        tree.root1.right = new Node(3);
        tree.root1.left.left = new Node(4);
        tree.root1.left.right = new Node(5);

        tree.root2 = new Node(1);
        tree.root2.left = new Node(2);
        tree.root2.right = new Node(3);
        tree.root2.left.left = new Node(4);
        tree.root2.left.right = new Node(5);

          // Function call
        if (tree.identicalTrees(tree.root1, tree.root2)) {
            Console.WriteLine("Both trees are identical");
        }
        else {
            Console.WriteLine("Trees are not identical");
        }
    }
}

// This code is contributed by Shrikant13
Javascript 
<script>

    // JavaScript program to see if two trees are identical
    
    class Node
    {
        constructor(data) {
           this.left = null;
           this.right = null;
           this.data = data;
        }
    }
    
    let root1, root2;
   
    /* Given two trees, return true if they are
       structurally identical */
    function identicalTrees(a, b) 
    {
        /*1. both empty */
        if (a == null && b == null)
            return true;
              
        /* 2. both non-empty -> compare them */
        if (a != null && b != null) 
            return (a.data == b.data
                    && identicalTrees(a.left, b.left)
                    && identicalTrees(a.right, b.right));
   
        /* 3. one empty, one not -> false */
        return false;
    }
   
    root1 = new Node(1);
    root1.left = new Node(2);
    root1.right = new Node(3);
    root1.left.left = new Node(4);
    root1.left.right = new Node(5);

    root2 = new Node(1);
    root2.left = new Node(2);
    root2.right = new Node(3);
    root2.left.left = new Node(4);
    root2.left.right = new Node(5);

    if (identicalTrees(root1, root2))
      document.write("Both trees are identical");
    else
      document.write("Trees are not identical");
    
</script>

Output
Both trees are identical.

Time Complexity: O(min(N, M)), Where N and M are the sizes of the trees
Auxiliary Space: O(log min(N, M)), due to auxiliary stack space used by recursion calls

Write a function to determine if two trees are identical or not by comparing their traversals:

To solve the problem follow the below idea:

If two trees are identical, their preorder, inorder and postorder traversals will also be the same

Note: For this, we can find one traversal, say inorder, and if it is the same for both the trees, can we say the given trees are identical?  No, because we can have two trees with the same inorder traversal, still they can be non-identical.

See the below example:

Tree 1:    2                           Tree 2:   1
            /                                            \
         1                                                2

Both the trees have inorder traversal as “2  1”, but they are not identical.

To tackle such edge cases, we should find all the traversal for both the trees and see if they are equal. If yes, the given trees are identical else not.

Below is the implementation of this approach:

C++ 
/* CPP code to check if two trees are identical */
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node */
class Node {
public:
    int data;
    Node* left;
    Node* right;

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

// Utility function to check inorder traversal
void inOrder(Node* root, vector<int>& sol)
{
    if (root == NULL)
        return;
    inOrder(root->left, sol);
    sol.push_back(root->data);
    inOrder(root->right, sol);
}

// Utility function to check preorder traversal
void preOrder(Node* root, vector<int>& sol)
{

    if (root == NULL)
        return;
    sol.push_back(root->data);
    preOrder(root->left, sol);
    preOrder(root->right, sol);
}

// Utility function to check postorder traversal
void postOrder(Node* root, vector<int>& sol)
{

    if (root == NULL)
        return;
    postOrder(root->left, sol);
    postOrder(root->right, sol);
    sol.push_back(root->data);
}

// Function to check if two trees are identical
bool isIdentical(Node* root1, Node* root2)
{
    // Code Here
    // Create two vector to store traversals
    vector<int> res1;
    vector<int> res2;

    // check inOrder
    // cout<<"Hi"<<" ";
    inOrder(root1, res1);
    inOrder(root2, res2);
    if (res1 != res2)
        return false;

    // clear previous result to reuse vector
    res1.clear();
    res2.clear();
    // check PreOrder
    preOrder(root1, res1);
    preOrder(root2, res2);
    if (res1 != res2)
        return false;

    // clear previous result to reuse vector
    res1.clear();
    res2.clear();
    // check PostOrder
    postOrder(root1, res1);
    postOrder(root2, res2);
    if (res1 != res2)
        return false;

    return true;
}

// Driver code
int main()
{
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);

    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    root2->left->left = new Node(4);
    root2->left->right = new Node(5);
    // Function call
    if (isIdentical(root1, root2)) {
        cout << "Both the trees are identical." << endl;
    }
    else {
        cout << "Given trees are not identical." << endl;
    }

    return 0;
}

// This code is contributed by adityamaharshi21
Java 
/* java code to check if two trees are identical */

import java.io.*;
import java.util.*;

public class GFG {

    /* A binary tree node */
    static class Node {
        int data;
        Node left, right;
        public Node(int data) { this.data = data; }
    }

    // Driver code
    public static void main(String[] args)
    {
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);

        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

          // Function call
        if (isIdentical(root1, root2)) {
            System.out.println(
                "Both the trees are identical.");
        }
        else {
            System.out.println(
                "Given trees are not identical.");
        }
    }

    // Function to check if two trees are identical
    static boolean isIdentical(Node root1, Node root2)
    {
        // Code Here
        // Create two arraylist to store traversals
        ArrayList<Integer> res1 = new ArrayList<Integer>();
        ArrayList<Integer> res2 = new ArrayList<Integer>();

        // check inOrder
        inOrder(root1, res1);
        inOrder(root2, res2);
        if (!res1.equals(res2))
            return false;

        // clear previous result to reuse arraylist
        res1.clear();
        res2.clear();
        // check PreOrder
        preOrder(root1, res1);
        preOrder(root2, res2);
        if (!res1.equals(res2))
            return false;

        // clear previous result to reuse arraylist
        res1.clear();
        res2.clear();
        // check PostOrder
        postOrder(root1, res1);
        postOrder(root2, res2);
        if (!res1.equals(res2))
            return false;

        return true;
    }

    // Utility function to check inorder traversal
    static void inOrder(Node root, ArrayList<Integer> sol)
    {
        if (root == null)
            return;
        inOrder(root.left, sol);
        sol.add(root.data);
        inOrder(root.right, sol);
    }

    // Utility function to check preorder traversal
    static void preOrder(Node root, ArrayList<Integer> sol)
    {

        if (root == null)
            return;
        sol.add(root.data);
        preOrder(root.left, sol);
        preOrder(root.right, sol);
    }

    // Utility function to check postorder traversal
    static void postOrder(Node root, ArrayList<Integer> sol)
    {

        if (root == null)
            return;
        postOrder(root.left, sol);
        postOrder(root.right, sol);
        sol.add(root.data);
    }
}
Python 
# Python program to check if two trees are identical

# A binary tree node
class Node:
    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None

# Utility function to check inorder traversal      
def inOrder(root, sol):
    if root is None:
        return
    inOrder(root.left, sol)
    sol.append(root.data)
    inOrder(root.right, sol)
    
# Utility function to check preorder traversal
def preOrder(root, sol):
    if root is None:
        return
    sol.append(root.data)
    preOrder(root.left, sol)
    preOrder(root.right, sol)

# Utility function to check postorder traversal
def postOrder(root, sol):
    if root is None:
        return
    postOrder(root.left, sol)
    postOrder(root.right, sol)
    sol.append(root.data)

# Function to check if two trees are identical
def isIdentical(root1, root2):
    # Code here
    # Create two vector to store traversal
    res1 = []
    res2 = []
    
    #check inorder
    inOrder(root1, res1)
    inOrder(root2, res2)
    if res1 != res2:
        return False
    
    # clear previous result to reuse vector
    res1.clear()
    res2.clear()
    # check PreOrder
    preOrder(root1, res1)
    preOrder(root2, res2)
    if res1 != res2:
        return False
    
    # clear previous result to reuse vector
    res1.clear()
    res2.clear()
    # check PostOrder
    postOrder(root1, res1)
    postOrder(root2, res2)
    if res1 != res2:
        return False
    
    return True
    
# Driver code
if __name__ == '__main__':
    root1 = Node(1)
    root1.left = Node(2)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(5)
    
    root2 = Node(1)
    root2.left = Node(2)
    root2.right = Node(3)
    root2.left.left = Node(4)
    root2.left.right = Node(5)
    
    # Function Call
    if isIdentical(root1, root2):
        print("Both the trees are identical.")
    else:
        print("Given trees are not identical")
    
# This code is contributed by Yash Agarwal(yashagarwal2852002)
C# 
/* C# code to check if two trees are identical */
using System;
using System.Collections.Generic;

public class GFG {

  /* A binary tree node */
  class Node {
    public int data;
    public Node left, right;
    public Node(int data) { this.data = data; }
  }

  // Driver code
  public static void Main(String[] args)
  {
    Node root1 = new Node(1);
    root1.left = new Node(2);
    root1.right = new Node(3);
    root1.left.left = new Node(4);
    root1.left.right = new Node(5);

    Node root2 = new Node(1);
    root2.left = new Node(2);
    root2.right = new Node(3);
    root2.left.left = new Node(4);
    root2.left.right = new Node(5);

    // Function call
    if (isIdentical(root1, root2)) {
      Console.WriteLine(
        "Both the trees are identical.");
    }
    else {
      Console.WriteLine(
        "Given trees are not identical.");
    }
  }

  // Function to check if two trees are identical
  static bool isIdentical(Node root1, Node root2)
  {
    // Code Here
    // Create two arraylist to store traversals
    List<int> res1 = new List<int>();
    List<int> res2 = new List<int>();

    // check inOrder
    inOrder(root1, res1);
    inOrder(root2, res2);
    if (!res1.Equals(res2))
      return false;

    // clear previous result to reuse arraylist
    res1.Clear();
    res2.Clear();
    // check PreOrder
    preOrder(root1, res1);
    preOrder(root2, res2);
    if (!res1.Equals(res2))
      return false;

    // clear previous result to reuse arraylist
    res1.Clear();
    res2.Clear();
    // check PostOrder
    postOrder(root1, res1);
    postOrder(root2, res2);
    if (!res1.Equals(res2))
      return false;

    return true;
  }

  // Utility function to check inorder traversal
  static void inOrder(Node root, List<int> sol)
  {
    if (root == null)
      return;
    inOrder(root.left, sol);
    sol.Add(root.data);
    inOrder(root.right, sol);
  }

  // Utility function to check preorder traversal
  static void preOrder(Node root, List<int> sol)
  {

    if (root == null)
      return;
    sol.Add(root.data);
    preOrder(root.left, sol);
    preOrder(root.right, sol);
  }

  // Utility function to check postorder traversal
  static void postOrder(Node root, List<int> sol)
  {

    if (root == null)
      return;
    postOrder(root.left, sol);
    postOrder(root.right, sol);
    sol.Add(root.data);
  }
}

// This code is contributed adityamaharshi21
Javascript 
// JavaScript program for above approach
class Node {
    constructor(d) {
        this.data = d;
        this.left = null;
        this.right = null;
    }
}

// Utility function to check inorder traversal
function inOrder(root, sol) {
    if (root == null) return;
    inOrder(root.left, sol);
    sol.push(root.data);
    inOrder(root.right, sol);
}

// Utility function to check preorder traversal
function preOrder(root, sol) {
    if (root == null) return;
    sol.push(root.data);
    preOrder(root.left, sol);
    preOrder(root.right, sol);
}

// Utility function to check postorder traversal
function postOrder(root, sol) {
    if (root == null) return;
    postOrder(root.left, sol);
    postOrder(root.right, sol);
    sol.push(root.data);
}

// Function to check if two trees are identical
function isIdentical(root1, root2) {
    // Code Here
    // Create two vector to store traversals
    let res1 = [];
    let res2 = [];

    // check inOrder
    inOrder(root1, res1);
    inOrder(root2, res2);
    if (res1.toString() != res2.toString()) return false;

    // clear previous result to reuse vector
    res1 = [];
    res2 = [];
    // check PreOrder
    preOrder(root1, res1);
    preOrder(root2, res2);
    if (res1.toString() != res2.toString()) return false;

    // clear previous result to reuse vector
    res1 = [];
    res2 = [];
    // check PostOrder
    postOrder(root1, res1);
    postOrder(root2, res2);
    if (res1.toString() != res2.toString()) return false;

    return true;
}

// Driver code
let root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);

let root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);
// Function call
if (isIdentical(root1, root2)) {
    console.log("Both the trees are identical.");
} 
else {
    console.log("Given trees are not identical.");
}

// This code is contributed by adityamaharshi

Output
Both the trees are identical.

Time complexity: O(N)
Auxiliary Space: O(N), since using auxiliary ArrayList and call stack

The Way We Can Determine Trees are Identical Only Using Pre-Order Traversal:

 The Approach:

          Here in this Approach we are storing preorder traversal of tree where we store zero(0)(we can store any another number so that we donot miss any node such as INT_MAX or -10000) for the null node and then we compare both vector if they are same then return true both the trees are identical.

C++ 
/* CPP code to check if two trees are identical */
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node */
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int d)
    {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};
void preorder(Node* root,vector<int>&v){
      if(root==NULL){
         // v.push_back(0);
          return;
      }
      v.push_back(root->data);
      if(root->left)preorder(root->left,v);
      if(!root->left)v.push_back(0);
      if(root->right)preorder(root->right,v);
       if(!root->right)v.push_back(0);
  }

bool isIdentical(Node* root1,Node*root2){
  vector<int>v,x;
  preorder(root1,v);
  preorder(root2,x);
       // for(auto it:v)cout<<it<<" ";
       // cout<<endl;
  return v==x;
}

int main() {
  Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);

    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    root2->left->left = new Node(4);
    root2->left->right = new Node(5);
    // Function call
    if (isIdentical(root1, root2)) {
        cout << "Both the trees are identical." << endl;
    }
    else {
        cout << "Given trees are not identical." << endl;
    }
}
Java 
// Java code for the above approach
import java.util.Vector;

/* A binary tree node */
class Node {
  int data;
  Node left;
  Node right;

  Node(int d) {
    this.data = d;
    this.left = null;
    this.right = null;
  }
}

public class Main {

  /* Function to traverse the tree in pre-order */
  public void preorder(Node root, Vector<Integer> v) {
    if (root == null) {
      // v.add(0);
      return;
    }
    v.add(root.data);
    if (root.left != null) {
      preorder(root.left, v);
    } else {
      v.add(0);
    }
    if (root.right != null) {
      preorder(root.right, v);
    } else {
      v.add(0);
    }
  }

  /* Function to check if two trees are identical */
  public boolean isIdentical(Node root1, Node root2) {
    Vector<Integer> v = new Vector<Integer>();
    Vector<Integer> x = new Vector<Integer>();
    preorder(root1, v);
    preorder(root2, x);
    // for (Integer it : v) {
    //     System.out.print(it + " ");
    // }
    // System.out.println();
    return v.equals(x);
  }

  public static void main(String[] args) {
    Node root1 = new Node(1);
    root1.left = new Node(2);
    root1.right = new Node(3);
    root1.left.left = new Node(4);
    root1.left.right = new Node(5);

    Node root2 = new Node(1);
    root2.left = new Node(2);
    root2.right = new Node(3);
    root2.left.left = new Node(4);
    root2.left.right = new Node(5);

    Main main = new Main();
    // Function call
    if (main.isIdentical(root1, root2)) {
      System.out.println("Both the trees are identical.");
    } else {
      System.out.println("Given trees are not identical.");
    }
  }
}

// This code is contributed by lokeshpotta20.
Python 
class Node:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None

def preorder(root, v):
    if root == None:
        return
    v.append(root.data)
    if root.left:
        preorder(root.left, v)
    else:
        v.append(0)
    if root.right:
        preorder(root.right, v)
    else:
        v.append(0)

def isIdentical(root1, root2):
    v = []
    x = []
    preorder(root1, v)
    preorder(root2, x)
    return v == x

root1 = Node(1)
root1.left = Node(2)
root1.right = Node(3)
root1.left.left = Node(4)
root1.left.right = Node(5)

root2 = Node(1)
root2.left = Node(2)
root2.right = Node(3)
root2.left.left = Node(4)
root2.left.right = Node(5)

if isIdentical(root1, root2):
    print("Both the trees are identical.")
else:
    print("Given trees are not identical.")
C# 
// C# program to see if two trees are identical
using System;
using System.Linq;
using System.Collections.Generic;

// A binary tree node
public class Node{
    public int data;
    public Node left, right;
 
    public Node(int item){
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    public Node root1, root2;
 
    public void preorder(Node root, List<int> v){
        if(root == null) return;
        v.Add(root.data);
        if(root.left != null) preorder(root.left, v);
        if(root.left == null) v.Add(0);
        if(root.right != null) preorder(root.right, v);
        if(root.right == null) v.Add(0);
    }
    
    public bool isIdentical(Node root1, Node root2){
        List<int> v = new List<int>();
        List<int> x = new List<int>();
        preorder(root1, v);
        preorder(root2, x);
        return Enumerable.SequenceEqual(v, x);
    }
 
    public static void Main(string[] args){
        BinaryTree tree = new BinaryTree();
 
        tree.root1 = new Node(1);
        tree.root1.left = new Node(2);
        tree.root1.right = new Node(3);
        tree.root1.left.left = new Node(4);
        tree.root1.left.right = new Node(5);
 
        tree.root2 = new Node(1);
        tree.root2.left = new Node(2);
        tree.root2.right = new Node(3);
        tree.root2.left.left = new Node(4);
        tree.root2.left.right = new Node(5);
 
          // Function call
        if (tree.isIdentical(tree.root1, tree.root2)) {
            Console.WriteLine("Both the trees are identical.");
        }
        else {
            Console.WriteLine("Given trees are not identical.");
        }
    }
}
 // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999)
Javascript 
/* Javascript code to check if two trees are identical */

/* A binary tree node */
class Node {
    constructor(d) {
        this.data = d;
        this.left = null;
        this.right = null;
    }
}

function preorder( root, v){
      if(root==null){
         // v.push_back(0);
          return;
      }
      v.push(root.data);
      if(root.left)
        preorder(root.left,v);
      if(!root.left)
        v.push(0);
      if(root.right)
        preorder(root.right,v);
       if(!root.right)
        v.push(0);
  }

function isIdentical( root1,root2){
  let v=[];
  let x=[];
  preorder(root1,v);
  preorder(root2,x);
  if(v.length!=x.length)
    return 0;
  for(let i=0; i<v.length; i++)
    if(x[i]!=v[i])
        return 0;
    return 1;
}

let root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);

let root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);
// Function call
if (isIdentical(root1, root2)) {
    console.log("Both the trees are identical.\n");
}
else {
    console.log("Given trees are not identical.\n");
}

Output
Both the trees are identical.

Time complexity: O(N)+O(M)
Auxiliary Space: O(N)+O(M) for vectors.

Using the Level Order traversal: 

The idea behind this approach to solve the above problem is to traverse both trees level by level and compare the values of the nodes at each level. We can use a queue to store the nodes of both trees in a level order manner.

Follow the below steps to implement the above idea:

  • Enqueue the root nodes of both trees into a queue.
  • While the queue is not empty, dequeue the front nodes of both trees and compare their values.
  • If the values are not equal, return false.
  • If the values are equal, enqueue the left and right child nodes of both trees, if they exist, into the queue.
  • Repeat steps 2-4 until either the queue becomes empty or we find two nodes with unequal values.
  • If the queue becomes empty and we have not found any nodes with unequal values, return true indicating that the trees are identical.

Below is the implementation of the above approach:

C++ 
// C++ code to implement the Level order traversal approach
#include <iostream>
#include <queue>

using namespace std;

// Definition of a Binary Tree Node
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val)
    {
        data = val;
        left = NULL;
        right = NULL;
    }
};

// Function to check if two trees are identical or not
bool isIdentical(Node* root1, Node* root2)
{
    // Base case: if both roots are NULL, then trees are
    // identical
    if (root1 == NULL && root2 == NULL)
        return true;

    // If one of the roots is NULL, then trees are not
    // identical
    if (root1 == NULL || root2 == NULL)
        return false;

    // Create queues to perform level order traversal on
    // both trees
    queue<Node*> q1, q2;

    // Add the roots of both trees to their respective
    // queues
    q1.push(root1);
    q2.push(root2);

    // Loop until either of the queues becomes empty
    while (!q1.empty() && !q2.empty()) {
        // Get the front node from both queues
        Node* curr1 = q1.front();
        q1.pop();
        Node* curr2 = q2.front();
        q2.pop();

        // If the data of the current nodes is not equal,
        // then trees are not identical
        if (curr1->data != curr2->data)
            return false;

        // If the left child of one tree exists and the left
        // child of the other tree does not exist, then
        // trees are not identical
        if (curr1->left != NULL && curr2->left == NULL)
            return false;
        if (curr1->left == NULL && curr2->left != NULL)
            return false;

        // If the right child of one tree exists and the
        // right child of the other tree does not exist,
        // then trees are not identical
        if (curr1->right != NULL && curr2->right == NULL)
            return false;
        if (curr1->right == NULL && curr2->right != NULL)
            return false;

        // If both left and right children of both trees
        // exist, then add them to their respective queues
        if (curr1->left != NULL && curr2->left != NULL) {
            q1.push(curr1->left);
            q2.push(curr2->left);
        }
        if (curr1->right != NULL && curr2->right != NULL) {
            q1.push(curr1->right);
            q2.push(curr2->right);
        }
    }

    // If we have reached this point, then trees are
    // identical
    return true;
}
// Driver Code
int main()
{
    // Create the first tree
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);

    // Create the second tree
    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    root2->left->left = new Node(4);
    root2->left->right = new Node(5);

    // Check if the trees are identical or not
    if (isIdentical(root1, root2))
        cout << "The trees are identical" << endl;
    else
        cout << "The trees are not identical" << endl;

    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot
Java 
/*package whatever //do not write package name here */

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left;
    Node right;

    Node(int val)
    {
        data = val;
        left = null;
        right = null;
    }
}

public class IdenticalTrees {
    public static boolean isIdentical(Node root1,
                                      Node root2)
    {
        if (root1 == null && root2 == null) {
            // Base case: if both roots are null, then trees
            // are identical
            return true;
        }

        if (root1 == null || root2 == null) {
            // If one of the roots is null, then trees are
            // not identical
            return false;
        }

        Queue<Node> q1 = new LinkedList<Node>();
        Queue<Node> q2 = new LinkedList<Node>();
        q1.add(root1);
        q2.add(root2);

        while (!q1.isEmpty() && !q2.isEmpty()) {
            Node curr1 = q1.poll();
            Node curr2 = q2.poll();

            if (curr1.data != curr2.data) {
                // If the data of the current nodes is not
                // equal, then trees are not identical
                return false;
            }

            if (curr1.left != null && curr2.left == null
                || curr1.left == null
                       && curr2.left != null) {
                // If the left child of one tree exists and
                // the left child of the other tree does not
                // exist, then trees are not identical
                return false;
            }

            if (curr1.right != null && curr2.right == null
                || curr1.right == null
                       && curr2.right != null) {
                // If the right child of one tree exists and
                // the right child of the other tree does
                // not exist, then trees are not identical
                return false;
            }

            if (curr1.left != null && curr2.left != null) {
                q1.add(curr1.left);
                q2.add(curr2.left);
            }

            if (curr1.right != null
                && curr2.right != null) {
                q1.add(curr1.right);
                q2.add(curr2.right);
            }
        }

        // If we have reached this point, then trees are
        // identical
        return true;
    }

    public static void main(String[] args)
    {
        // Create the first tree
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);

        // Create the second tree
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

        // Check if the trees are identical or not
        if (isIdentical(root1, root2)) {
            System.out.println("The trees are identical");
        }
        else {
            System.out.println(
                "The trees are not identical");
        }
    }
}
Python 
# Python code to implement the Level order traversal approach
from queue import Queue

# Definition of a Binary Tree Node
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

# Function to check if two trees are identical or not
def isIdentical(root1, root2):
    # Base case: if both roots are None, then trees are
    # identical
    if not root1 and not root2:
        return True

    # If one of the roots is None, then trees are not
    # identical
    if not root1 or not root2:
        return False

    # Create queues to perform level order traversal on
    # both trees
    q1 = Queue()
    q2 = Queue()

    # Add the roots of both trees to their respective
    # queues
    q1.put(root1)
    q2.put(root2)

    # Loop until either of the queues becomes empty
    while not q1.empty() and not q2.empty():
        # Get the front node from both queues
        curr1 = q1.get()
        curr2 = q2.get()

        # If the data of the current nodes is not equal,
        # then trees are not identical
        if curr1.data != curr2.data:
            return False

        # If the left child of one tree exists and the left
        # child of the other tree does not exist, then
        # trees are not identical
        if (curr1.left and not curr2.left) or (not curr1.left and curr2.left):
            return False

        # If the right child of one tree exists and the
        # right child of the other tree does not exist,
        # then trees are not identical
        if (curr1.right and not curr2.right) or (not curr1.right and curr2.right):
            return False

        # If both left and right children of both trees
        # exist, then add them to their respective queues
        if curr1.left and curr2.left:
            q1.put(curr1.left)
            q2.put(curr2.left)
        if curr1.right and curr2.right:
            q1.put(curr1.right)
            q2.put(curr2.right)

    # If we have reached this point, then trees are
    # identical
    return True

# Driver Code
if __name__ == '__main__':
    # Create the first tree
    root1 = Node(1)
    root1.left = Node(2)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(5)

    # Create the second tree
    root2 = Node(1)
    root2.left = Node(2)
    root2.right = Node(3)
    root2.left.left = Node(4)
    root2.left.right = Node(5)

    # Check if the trees are identical or not
    if isIdentical(root1, root2):
        print("The trees are identical")
    else:
        print("The trees are not identical")

#This code is contributed by shivamsharma215
C# 
using System;
using System.Collections.Generic;

// Definition of a Binary Tree Node
public class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int val)
    {
        data = val;
        left = null;
        right = null;
    }
};

public class Gfg {
    // Function to check if two trees are identical or not
    public static bool isIdentical(Node root1, Node root2)
    {
        // Base case: if both roots are null, then trees are
        // identical
        if (root1 == null && root2 == null)
            return true;

        // If one of the roots is null, then trees are not
        // identical
        if (root1 == null || root2 == null)
            return false;

        // Create queues to perform level order traversal on
        // both trees
        Queue<Node> q1 = new Queue<Node>();
        Queue<Node> q2 = new Queue<Node>();

        // Add the roots of both trees to their respective
        // queues
        q1.Enqueue(root1);
        q2.Enqueue(root2);

        // Loop until either of the queues becomes empty
        while (q1.Count != 0 && q2.Count != 0) {
            // Get the front node from both queues
            Node curr1 = q1.Dequeue();
            Node curr2 = q2.Dequeue();

            // If the data of the current nodes is not equal,
            // then trees are not identical
            if (curr1.data != curr2.data)
                return false;

            // If the left child of one tree exists and the left
            // child of the other tree does not exist, then
            // trees are not identical
            if (curr1.left != null && curr2.left == null)
                return false;
            if (curr1.left == null && curr2.left != null)
                return false;

            // If the right child of one tree exists and the
            // right child of the other tree does not exist,
            // then trees are not identical
            if (curr1.right != null && curr2.right == null)
                return false;
            if (curr1.right == null && curr2.right != null)
                return false;

            // If both left and right children of both trees
            // exist, then add them to their respective queues
            if (curr1.left != null && curr2.left != null) {
                q1.Enqueue(curr1.left);
                q2.Enqueue(curr2.left);
            }
            if (curr1.right != null && curr2.right != null) {
                q1.Enqueue(curr1.right);
                q2.Enqueue(curr2.right);
            }
        }

        // If we have reached this point, then trees are
        // identical
        return true;
    }

    // Driver Code
    static void Main()
    {
        // Create the first tree
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);

        // Create the second tree
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

        // Check if the trees are identical or not
        if (isIdentical(root1, root2))
            Console.WriteLine("The trees are identical");
        else
            Console.WriteLine("The trees are not identical");
    }
}
Javascript 
// JavaScript code to implement the Level order traversal approach
// Definition of a Binary Tree Node
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

// Function to check if two trees are identical or not
function isIdentical(root1, root2) {
    // Base case: if both roots are null, then trees are identical
    if (!root1 && !root2)
        return true; // If one of the roots is null, then trees are not identical
    if (!root1 || !root2)
        return false;

    // Create queues to perform level order traversal on both trees
    const q1 = [],
        q2 = [];

    // Add the roots of both trees to their respective queues
    q1.push(root1);
    q2.push(root2);

    // Loop until either of the queues becomes empty
    while (q1.length && q2.length) {
        // Get the front node from both queues
        const curr1 = q1.shift();
        const curr2 = q2.shift();

        // If the data of the current nodes is not equal, then trees are not identical
        if (curr1.data !== curr2.data)
            return false;

        // If the left child of one tree exists and the left child of the other tree does not exist, then trees are not identical
        if (curr1.left && !curr2.left)
            return false;
        if (!curr1.left && curr2.left)
            return false;

        // If the right child of one tree exists and the right child of the other tree does not exist, then trees are not identical
        if (curr1.right && !curr2.right)
            return false;
        if (!curr1.right && curr2.right)
            return false;

        // If both left and right children of both trees exist, then add them to their respective queues
        if (curr1.left && curr2.left) {
            q1.push(curr1.left);
            q2.push(curr2.left);
        }
        if (curr1.right && curr2.right) {
            q1.push(curr1.right);
            q2.push(curr2.right);
        }
    }

    // If we have reached this point, then trees are identical
    return true;
}

// Driver Code
// Create the first tree
const root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);

// Create the second tree
const root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);

// Check if the trees are identical or not
if (isIdentical(root1, root2))
    console.log("The trees are identical");
else
    console.log("The trees are not identical");

Output
The trees are identical

Time complexity: O(N) , the time complexity will be proportional to the total number of nodes.
Auxiliary Space: O(N), The auxiliary space complexity of the level order traversal approach is O(n), where n is the total number of nodes in both trees.

Using the Morris traversal: 

The basic idea behind the Morris traversal approach to solve the problem of checking if two binary trees are identical is to use the Morris traversal algorithm to traverse both trees in-order simultaneously, and compare the nodes visited at each step.

Follow the steps to implement the above idea:

  1. Check if both trees are empty. If they are, return true. If only one of them is empty, return false.
  2. Perform the Morris traversal for in-order traversal of both trees simultaneously. At each step, compare the nodes visited in both trees.
  3. If at any step, the nodes visited in both trees are not equal, return false.
  4. If we reach the end of both trees simultaneously (i.e., both nodes are NULL), return true.

Below is the implementation of the above idea:

C++ 
// C++ code to implement the Morris traversal approach

#include <iostream>
using namespace std;

/* A binary tree node */
struct Node {
    int data;
    Node *left, *right;
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};

/* Morris traversal approach to check if two binary trees
 * are identical */
bool isIdentical(Node* r1, Node* r2)
{
    // Base cases
    if (r1 == NULL && r2 == NULL) // both trees are empty
        return true;
    if (r1 == NULL
        || r2 == NULL) // one of the trees is empty, which
                       // means they are not identical
        return false;

    // Morris traversal
    while (r1 != NULL && r2 != NULL) {
        if (r1->data
            != r2->data) // if the data of the current nodes
                         // is not the same, then the trees
                         // are not identical
            return false;

        // Morris traversal for r1
        if (r1->left
            == NULL) { // if the left child is NULL, move to
                       // the right child
            r1 = r1->right;
        }
        else { // if the left child is not NULL, find the
               // predecessor
            Node* pre = r1->left;
            while (pre->right != NULL
                   && pre->right
                          != r1) // find the rightmost node
                                 // in the left subtree
                pre = pre->right;
            if (pre->right
                == NULL) { // if the right pointer of the
                           // predecessor is NULL, make it
                           // point to the current node
                pre->right = r1;
                r1 = r1->left;
            }
            else { // if the right pointer of the
                   // predecessor is already pointing to the
                   // current node, set it back to NULL and
                   // move to the right child
                pre->right = NULL;
                r1 = r1->right;
            }
        }

        // Morris traversal for r2, same as for r1
        if (r2->left == NULL) {
            r2 = r2->right;
        }
        else {
            Node* pre = r2->left;
            while (pre->right != NULL && pre->right != r2)
                pre = pre->right;
            if (pre->right == NULL) {
                pre->right = r2;
                r2 = r2->left;
            }
            else {
                pre->right = NULL;
                r2 = r2->right;
            }
        }
    }

    return (r1 == NULL
            && r2 == NULL); // if both r1 and r2 are NULL,
                            // then the trees are identical
}

/* Driver code */
int main()
{
    // Construct the first tree
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);

    // Construct the second tree
    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    root2->left->left = new Node(4);
    root2->left->right = new Node(5);

    // Check if the trees are identical
    if (isIdentical(root1, root2))
        cout << "Both trees are identical";
    else
        cout << "Both trees are not identical";

    return 0;
}
// This code is contributed by Veerendra_Singh_Rajpoot
Java 
// Java code to implement the Morris traversal approach

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class IdenticalBinaryTrees {
    // Morris traversal approach to check if two binary trees
    // are identical
    public static boolean isIdentical(Node r1, Node r2) {
        // Base cases
        if (r1 == null && r2 == null) // both trees are empty
            return true;
        if (r1 == null || r2 == null) // one of the trees is empty, which
                                     // means they are not identical
            return false;

        // Morris traversal
        while (r1 != null && r2 != null) {
            if (r1.data != r2.data) // if the data of the current nodes
                                    // is not the same, then the trees
                                    // are not identical
                return false;

            // Morris traversal for r1
            if (r1.left == null) { // if the left child is NULL, move to
                                   // the right child
                r1 = r1.right;
            } else { // if the left child is not NULL, find the
                     // predecessor
                Node pre = r1.left;
                while (pre.right != null && pre.right != r1) // find the rightmost node
                                                             // in the left subtree
                    pre = pre.right;
                if (pre.right == null) { // if the right pointer of the
                                         // predecessor is NULL, make it
                                         // point to the current node
                    pre.right = r1;
                    r1 = r1.left;
                } else { // if the right pointer of the
                         // predecessor is already pointing to the
                         // current node, set it back to NULL and
                         // move to the right child
                    pre.right = null;
                    r1 = r1.right;
                }
            }

            // Morris traversal for r2, same as for r1
            if (r2.left == null) {
                r2 = r2.right;
            } else {
                Node pre = r2.left;
                while (pre.right != null && pre.right != r2)
                    pre = pre.right;
                if (pre.right == null) {
                    pre.right = r2;
                    r2 = r2.left;
                } else {
                    pre.right = null;
                    r2 = r2.right;
                }
            }
        }

        return (r1 == null && r2 == null); // if both r1 and r2 are NULL,
                                          // then the trees are identical
    }

    // Driver code
    public static void main(String[] args) {
        // Construct the first tree
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);

        // Construct the second tree
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

        // Check if the trees are identical
        if (isIdentical(root1, root2))
            System.out.println("Both trees are identical");
        else
            System.out.println("Both trees are not identical");
    }
}
//This code is contributed by Veerendra_Singh_Rajpoot
Python 
# A binary tree node
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Morris traversal approach to check if two binary trees are identical


def isIdentical(r1, r2):
    # Base cases
    if not r1 and not r2:  # both trees are empty
        return True
    if not r1 or not r2:  # one of the trees is empty, which means they are not identical
        return False

    # Morris traversal
    while r1 and r2:
        if r1.data != r2.data:  # if the data of the current nodes is not the same, then the trees are not identical
            return False

        # Morris traversal for r1
        if not r1.left:  # if the left child is None, move to the right child
            r1 = r1.right
        else:  # if the left child is not None, find the predecessor
            pre = r1.left
            while pre.right and pre.right != r1:  # find the rightmost node in the left subtree
                pre = pre.right
            if not pre.right:  # if the right pointer of the predecessor is None, make it point to the current node
                pre.right = r1
                r1 = r1.left
            else:  # if the right pointer of the predecessor is already pointing to the current node, set it back to None and move to the right child
                pre.right = None
                r1 = r1.right

        # Morris traversal for r2, same as for r1
        if not r2.left:
            r2 = r2.right
        else:
            pre = r2.left
            while pre.right and pre.right != r2:
                pre = pre.right
            if not pre.right:
                pre.right = r2
                r2 = r2.left
            else:
                pre.right = None
                r2 = r2.right

    return not r1 and not r2  # if both r1 and r2 are None, then the trees are identical


# Driver code
if __name__ == "__main__":
    # Construct the first tree
    root1 = Node(1)
    root1.left = Node(2)
    root1.right = Node(3)
    root1.left.left = Node(4)
    root1.left.right = Node(5)

    # Construct the second tree
    root2 = Node(1)
    root2.left = Node(2)
    root2.right = Node(3)
    root2.left.left = Node(4)
    root2.left.right = Node(5)

    # Check if the trees are identical
    if isIdentical(root1, root2):
        print("Both trees are identical")
    else:
        print("Both trees are not identical")

# This code is contributed by rambabuguphka
C# 
using System;

public class Node
{
    public int data;
    public Node left, right;

    public Node(int x)
    {
        data = x;
        left = right = null;
    }
}

public class IdenticalTrees
{   
    // Morris traversal approach to check if two binary trees
    // * are identical
    public static bool IsIdentical(Node r1, Node r2)
    {   
        // Base cases
        if (r1 == null && r2 == null) // both trees are empty
            return true;
        if (r1 == null || r2 == null) // one of the trees is empty
            return false;

        while (r1 != null && r2 != null)
        {
            if (r1.data != r2.data) // if the data of the current nodes is not the same
                return false;

            // Morris traversal for r1
            if (r1.left == null)
            {
                r1 = r1.right;
            }
            else
            {
                Node pre = r1.left;
                while (pre.right != null && pre.right != r1)
                    pre = pre.right;

                if (pre.right == null)
                {
                    pre.right = r1;
                    r1 = r1.left;
                }
                else
                {
                    pre.right = null;
                    r1 = r1.right;
                }
            }

            // Morris traversal for r2, same as for r1
            if (r2.left == null)
            {
                r2 = r2.right;
            }
            else
            {
                Node pre = r2.left;
                while (pre.right != null && pre.right != r2)
                    pre = pre.right;

                if (pre.right == null)
                {
                    pre.right = r2;
                    r2 = r2.left;
                }
                else
                {
                    pre.right = null;
                    r2 = r2.right;
                }
            }
        }

        return r1 == null && r2 == null; // if both r1 and r2 are null, 
                                         // then the trees are identical
    }

    public static void Main(string[] args)
    {
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);

        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);

        if (IsIdentical(root1, root2))
            Console.WriteLine("Both trees are identical");
        else
            Console.WriteLine("Both trees are not identical");
    }
}
// This code is contributed by rambabuguphka
Javascript 
// Javascript code to implement the Morris traversal approach

class Node {
    constructor(item) {
        this.data = item;
        this.left = null;
        this.right = null;
    }
}

// Morris traversal approach to check if two binary trees are identical
function isIdentical(r1, r2) {
    if (r1 === null && r2 === null) {
        return true;
    }
    if (r1 === null || r2 === null) {
        return false;
    }

    // Morris traversal
    while (r1 !== null && r2 !== null) {
        if (r1.data !== r2.data) {
            return false;
        }

        // Morris traversal for r1
        if (r1.left === null) {
            r1 = r1.right;
        } else {
            let pre = r1.left;
            while (pre.right !== null && pre.right !== r1) {
                pre = pre.right;
            }

            if (pre.right === null) {
                pre.right = r1;
                r1 = r1.left;
            } else {
                pre.right = null;
                r1 = r1.right;
            }
        }

        // Morris traversal for r2
        if (r2.left === null) {
            r2 = r2.right;
        } else {
            let pre = r2.left;
            while (pre.right !== null && pre.right !== r2) {
                pre = pre.right;
            }

            if (pre.right === null) {
                pre.right = r2;
                r2 = r2.left;
            } else {
                pre.right = null;
                r2 = r2.right;
            }
        }
    }

    return r1 === null && r2 === null; // if both r1 and r2 are NULL
                                       // then the trees are identical
}

// Construct the first tree
const root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(3);
root1.left.left = new Node(4);
root1.left.right = new Node(5);

// Construct the second tree
const root2 = new Node(1);
root2.left = new Node(2);
root2.right = new Node(3);
root2.left.left = new Node(4);
root2.left.right = new Node(5);

// Check if the trees are identical
if (isIdentical(root1, root2)) {
    console.log("Both trees are identical");
} else {
    console.log("Both trees are not identical");
}

// This code is contributed by guptapratik

Output
Both trees are identical

Time Complexity: O(N) ,The time complexity of the Morris traversal approach for checking if two binary trees are identical is O(n), where n is the total number of nodes in the trees. This is because each node is visited only once, and the traversal does not involve any recursion or extra data structures.

Auxiliary Space: O(1) , The space complexity of the Morris traversal approach is O(1), which means that the space required by the algorithm is constant and does not depend on the size of the input. This is because the traversal only requires a few pointers to the tree nodes and does not use any additional data structures, such as stacks or queues, to store intermediate results.

Related Article: Iterative function to check if two trees are identical.



https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Improve
Previous Article
Symmetric Tree (Mirror Image of itself)
Next Article
Subtree with given sum in a Binary Tree

Similar Reads

POTD Solutions | 21 Nov' 23 | Determine if Two Trees are Identical
View all POTD Solutions Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Binary Tree but will also help you build up problem-solving skills. We recommend you to try this problem
7 min read
Check whether the two Binary Search Trees are Identical or Not
Given the root nodes of the two binary search trees. The task is to print "Both BSTs are identical" if the two Binary Search Trees are identical else print "Both BSTs are identical". Two trees are identical if they are identical structurally and nodes have the same values. Tree1: 5 / \ 3 8 / \ 2 4 Tree2: 5 / \ 3 8 / \ 2 4 Here in both the trees the
15+ min read
Check if two Binary trees are identical after exactly K changes
Given two binary trees T1 and T2 and integer K, the task is to check whether both trees are identical or not after making exactly K changes in the first tree. In each change, one tree element can be converted into any other integer. Examples: Input: K = 1 T1 = 1 T2 = 1 / \ / \ 2 4 2 3Output: YesExplanation: Change the node with value 4 to value 3 I
9 min read
Iterative function to check if two trees are identical
Two trees are identical when they have same data and arrangement of data is also same. To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees. Examples: Input : Roots of below trees 10 10 / \ / 5 6 5 Output : falseInput : Roots of below trees 10 1
15+ min read
Check if given two straight lines are identical or not
Given two straight lines with co-efficients of their equations a1x + b1y + c1 = 0 and a2x + b2y + c2 = 0 respectively, the task is to check if the straight lines are identical or not. Examples: Input: a1 = -2, b1 = 4, c1 = 3, a2 = -6, b2 = 12, c2 = 9 Output: The given straight lines are identicalInput: a1 = 12, b1 = 3, c1 = 8, a2 = 7, b2 = -12, c2
5 min read
Check for Identical BSTs without building the trees
Given two arrays that represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree. Example: For example, the input arrays are {2, 4, 3, 1} and {2, 1, 4, 3} will construct the same tree Let the input arrays be a[] and b[] Ex
15 min read
Python List Equality | Program to check if two given matrices are identical
We are given two square matrices of same order. Check if two given matrices are identical. Examples: Input : A = [ [1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]] B = [ [1, 1, 1, 1], [2, 2, 2, 2], [3, 3, 3, 3], [4, 4, 4, 4]] Output: Matrices are identical We have existing solution for this problem please refer C Program to check if two give
3 min read
Program to check if two given matrices are identical
The below program checks if two square matrices of size 4*4 are identical or not. For any two matrices to be equal, a number of rows and columns in both the matrix should be equal and the corresponding elements should also be equal. Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Implementation: C/C++ Code // C++
6 min read
Determine whether the given Array forms a valley or not
Given an array arr[] of length N, the task is to check whether the given array forms a valley or not. An array is said to be a valley if there is a point till which the array is non-increasing and after that increases in nature. Formally arr[0] ? arr[1] ? . . . ? arr[i] ? arr[i+1] ? . . . ? arr[N-1] and arr[0] &gt; arr[i] and arr[i] &lt; arr[N-1],
6 min read
Determine whether the given integer N is a Peculiar Number or not
Given an integer N, our task is the determine if the integer N is Peculiar Number. If it is then print "yes" otherwise output "no".The peculiar number is the number which is three times the sum of digits of the number. Examples: Input: N = 27 Output: Yes Explanation: Digit sum for 27 is 9 and 3 * 9 = 27 which is equal to N. Hence the output is yes.
4 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox