Check if Two Trees are Identical

Last Updated : 7 Oct, 2025

Given the roots r1 and r2 of two binary trees, determine whether they are identical.
Two trees are considered identical if they have the same structure and the same node values.

Examples:

Input:

Output: true
Explanation: Trees are identical, having same node structure and node values.
Input:

Output: false
Explanation: Trees are not identical, both have different node structure.

Try it on GfG Practice

Table of Content

[Expected Approach - 1] Using DFS
[Expected Approach - 2] Using Level Order Traversal (BFS)
[Expected Approach - 3] Using Morris Traversal

[Approach - 1] Using Recursion (DFS)

The idea is to compare the root node's data and recursively verify that their left and right subtrees are identical. Both trees must have the same structure and data at each corresponding node.

C++

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node *left, *right;

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

bool isIdentical(Node* r1, Node* r2) {

    // If both trees are empty, they are identical
    if (r1 == nullptr && r2 == nullptr)
        return true;

    // If only one tree is empty, they are not identical
    if (r1 == nullptr || r2 == nullptr)
        return false;

    // Check if the root data is the same and
    // recursively check for the left and right subtrees
    return (r1->data == r2->data) &&
           isIdentical(r1->left, r2->left) &&
           isIdentical(r1->right, r2->right);
}

int main() {

    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    
    Node* r1 = new Node(1);    
    r1->left = new Node(2);   
    r1->right = new Node(3); 
    r1->left->left = new Node(4); 

    // Representation of input binary tree 2
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r2 = new Node(1);    
    r2->left = new Node(2);   
    r2->right = new Node(3);  
    r2->left->left = new Node(4);

    if (isIdentical(r1, r2))
        cout << "true\n";
    else
        cout << "false\n";

    return 0;
}

C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node *left, *right;
};

bool isIdentical(struct Node* r1, struct Node* r2) {

    // If both trees are empty, they are identical
    if (r1 == NULL && r2 == NULL)
        return true;

    // If only one tree is empty, they are not identical
    if (r1 == NULL || r2 == NULL)
        return false;

    // Check if the root data is the same and
    // recursively check for the left and right subtrees
    return (r1->data == r2->data) &&
           isIdentical(r1->left, r2->left) &&
           isIdentical(r1->right, r2->right);
}

struct Node* createNode(int val) {
    struct Node *newNode 
      = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {

    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    struct Node *r1 = createNode(1);
    r1->left = createNode(2);
    r1->right = createNode(3);
    r1->left->left = createNode(4);

    // Representation of input binary tree 2
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    struct Node *r2 = createNode(1);
    r2->left = createNode(2);
    r2->right = createNode(3);
    r2->left->left = createNode(4);

    if (isIdentical(r1, r2))
        printf("true\n");
    else
        printf("false\n");

    return 0;
}

Java

// Node structure
class Node {
    int data;
    Node left, right;

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

class GfG {

    static boolean isIdentical(Node r1, Node r2) {

        // If both trees are empty, they are identical
        if (r1 == null && r2 == null)
            return true;

        // If only one tree is empty, they are not identical
        if (r1 == null || r2 == null)
            return false;

        // Check if the root data is the same and
        // recursively check for the left and right subtrees
        return (r1.data == r2.data) &&
               isIdentical(r1.left, r2.left) &&
               isIdentical(r1.right, r2.right);
    }

    public static void main(String[] args) {

        // Representation of input binary tree 1
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r1 = new Node(1);
        r1.left = new Node(2);
        r1.right = new Node(3);
        r1.left.left = new Node(4);

        // Representation of input binary tree 2
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r2 = new Node(1);
        r2.left = new Node(2);
        r2.right = new Node(3);
        r2.left.left = new Node(4);

        if (isIdentical(r1, r2))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

# Node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

def isIdentical(r1, r2):
    # If both trees are empty, they are identical
    if r1 is None and r2 is None:
        return True

    # If only one tree is empty, they are not identical
    if r1 is None or r2 is None:
        return False

    # Check if the root data is the same and
    # recursively check for the left and right subtrees
    return (r1.data == r2.data and
            isIdentical(r1.left, r2.left) and
            isIdentical(r1.right, r2.right))

if __name__ == "__main__":

    # Representation of input binary tree 1
    #        1
    #       / \
    #      2   3
    #     /
    #    4
    r1 = Node(1)
    r1.left = Node(2)
    r1.right = Node(3)
    r1.left.left = Node(4)

    # Representation of input binary tree 2
    #        1
    #       / \
    #      2   3
    #     /
    #    4
    r2 = Node(1)
    r2.left = Node(2)
    r2.right = Node(3)
    r2.left.left = Node(4)

    if isIdentical(r1, r2):
        print("true")
    else:
        print("false")

C#

using System;

// Node structure
class Node {
    public int Data;
    public Node left, right;

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

class GfG {
    static bool isIdentical(Node r1, Node r2) {
        // If both trees are empty, they are identical
        if (r1 == null && r2 == null)
            return true;

        // If only one tree is empty, they are not identical
        if (r1 == null || r2 == null)
            return false;

        // Check if the root data is the same and
        // recursively check for the left and right subtrees
        return (r1.Data == r2.Data) &&
               isIdentical(r1.left, r2.left) &&
               isIdentical(r1.right, r2.right);
    }

    static void Main(string[] args) {

        // Representation of input binary tree 1
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r1 = new Node(1);
        r1.left = new Node(2);
        r1.right = new Node(3);
        r1.left.left = new Node(4);

        // Representation of input binary tree 2
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r2 = new Node(1);
        r2.left = new Node(2);
        r2.right = new Node(3);
        r2.left.left = new Node(4);

        if (isIdentical(r1, r2))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

JavaScript

// Node structure
class Node {
    constructor(val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

function isIdentical(r1, r2) {
    // If both trees are empty, they are identical
    if (r1 === null && r2 === null)
        return true;

    // If only one tree is empty, they are not identical
    if (r1 === null || r2 === null)
        return false;

    // Check if the root data is the same and
    // recursively check for the left and right subtrees
    return (r1.data === r2.data &&
            isIdentical(r1.left, r2.left) &&
            isIdentical(r1.right, r2.right));
}
//Driver Code
// Representation of input binary tree 1
//        1
//       / \
//      2   3
//     /
//    4
let r1 = new Node(1);
r1.left = new Node(2);
r1.right = new Node(3);
r1.left.left = new Node(4);

// Representation of input binary tree 2
//        1
//       / \
//      2   3
//     /
//    4
let r2 = new Node(1);
r2.left = new Node(2);
r2.right = new Node(3);
r2.left.left = new Node(4);

if (isIdentical(r1, r2)) {
    console.log("true");
} 
else {
    console.log("false");
}

Output

true

Time Complexity: O(n), where n is the number of nodes in the larger of the two trees, as each node is visited once.
Auxiliary Space: O(h), where h is the height of the trees, due to the recursive call stack.

[Approach - 2] Using Level Order Traversal (BFS)

The idea is to use level order traversal with two queues to compare the structure and data of two trees. By enqueuing nodes from both trees simultaneously, we can compare corresponding nodes at each level. If nodes at any level differ in data or structure, or if one tree has nodes where the other does not, the trees are not identical.

C++

#include <iostream>
#include <queue>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node *left, *right;
  
    Node(int val) {
        data = val;
        left = right = nullptr;
    }
};

bool isIdentical(Node* r1, Node* r2) {
    if (r1 == nullptr && r2 == nullptr)
        return true;

    if (r1 == nullptr || r2 == nullptr)
        return false;

    // Use two queues for level order traversal
    queue<Node*> q1, q2;
    q1.push(r1);
    q2.push(r2);

    while (!q1.empty() && !q2.empty()) {
        Node* node1 = q1.front();
        Node* node2 = q2.front();
        q1.pop();
        q2.pop();

        // Check if the current nodes are identical
        if (node1->data != node2->data)
            return false;

        // Check the left children
        if (node1->left && node2->left) {
            q1.push(node1->left);
            q2.push(node2->left);
        } else if (node1->left || node2->left) {
            return false;
        }

        // Check the right children
        if (node1->right && node2->right) {
            q1.push(node1->right);
            q2.push(node2->right);
        } else if (node1->right || node2->right) {
            return false;
        }
    }

    // If both queues are empty, the trees are identical
    return q1.empty() && q2.empty();
}

int main() {

    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r1 = new Node(1);    
    r1->left = new Node(2);   
    r1->right = new Node(3); 
    r1->left->left = new Node(4); 

    // Representation of input binary tree 2
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r2 = new Node(1);    
    r2->left = new Node(2);   
    r2->right = new Node(3);  
    r2->left->left = new Node(4);

    if (isIdentical(r1, r2))
        cout << "true\n";
    else
        cout << "false\n";

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node structure
struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} 

// Queue node for level order traversal
struct QueueNode {
    Node* treeNode;
    struct QueueNode* next;
}

// Queue structure
struct Queue {
    QueueNode* front;
    QueueNode* rear;
} 

// Create a new tree node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = val;
    node->left = node->right = NULL;
    return node;
}

// Queue functions
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

bool isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, Node* node) {
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->treeNode = node;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

Node* dequeue(Queue* q) {
    if (isEmpty(q))
        return NULL;
    QueueNode* temp = q->front;
    Node* node = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;
    free(temp);
    return node;
}

bool isIdentical(Node* r1, Node* r2) {
    if (r1 == NULL && r2 == NULL)
        return true;

    if (r1 == NULL || r2 == NULL)
        return false;

    // Use two queues for level order traversal
    Queue* q1 = createQueue();
    Queue* q2 = createQueue();
    enqueue(q1, r1);
    enqueue(q2, r2);

    while (!isEmpty(q1) && !isEmpty(q2)) {
        Node* node1 = dequeue(q1);
        Node* node2 = dequeue(q2);

        // Check if the current nodes are identical
        if (node1->data != node2->data)
            return false;

        // Check left children
        if (node1->left && node2->left) {
            enqueue(q1, node1->left);
            enqueue(q2, node2->left);
        } else if (node1->left || node2->left) {
            return false;
        }

        // Check right children
        if (node1->right && node2->right) {
            enqueue(q1, node1->right);
            enqueue(q2, node2->right);
        } else if (node1->right || node2->right) {
            return false;
        }
    }
    // If both queues are empty, the trees are identical
    return isEmpty(q1) && isEmpty(q2);
}

int main() {
    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r1 = newNode(1);
    r1->left = newNode(2);
    r1->right = newNode(3);
    r1->left->left = newNode(4);

    // Representation of input binary tree 2
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r2 = newNode(1);
    r2->left = newNode(2);
    r2->right = newNode(3);
    r2->left->left = newNode(4);

    if (isIdentical(r1, r2))
        printf("true\n");
    else
        printf("false\n");

    return 0;
}

Java

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

// Node structure
class Node {
    int data;
    Node left, right;

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

public class GFG {
    static boolean isIdentical(Node r1, Node r2) {
        if (r1 == null && r2 == null)
            return true;

        if (r1 == null || r2 == null)
            return false;

        // Use two queues for level order traversal
        Queue<Node> q1 = new LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();
        q1.add(r1);
        q2.add(r2);

        while (!q1.isEmpty() && !q2.isEmpty()) {
            Node node1 = q1.poll();
            Node node2 = q2.poll();

            // Check if the current nodes are identical
            if (node1.data != node2.data)
                return false;

            // Check the left children
            if (node1.left != null && node2.left != null) {
                q1.add(node1.left);
                q2.add(node2.left);
            } else if (node1.left != null || node2.left != null) {
                return false;
            }

            // Check the right children
            if (node1.right != null && node2.right != null) {
                q1.add(node1.right);
                q2.add(node2.right);
            } else if (node1.right != null || node2.right != null) {
                return false;
            }
        }

        // If both queues are empty, the trees are identical
        return q1.isEmpty() && q2.isEmpty();
    }

    public static void main(String[] args) {

        // Representation of input binary tree 1
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r1 = new Node(1);
        r1.left = new Node(2);
        r1.right = new Node(3);
        r1.left.left = new Node(4);

        // Representation of input binary tree 2
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r2 = new Node(1);
        r2.left = new Node(2);
        r2.right = new Node(3);
        r2.left.left = new Node(4);

        if (isIdentical(r1, r2))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

from collections import deque

# Node structure
class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

def isIdentical(r1, r2):
    if r1 is None and r2 is None:
        return True

    if r1 is None or r2 is None:
        return False

    # Use two queues for level order traversal
    q1 = deque()
    q2 = deque()
    q1.append(r1)
    q2.append(r2)

    while q1 and q2:
        node1 = q1.popleft()
        node2 = q2.popleft()

        # Check if the current nodes are identical
        if node1.data != node2.data:
            return False

        # Check the left children
        if node1.left and node2.left:
            q1.append(node1.left)
            q2.append(node2.left)
        elif node1.left or node2.left:
            return False

        # Check the right children
        if node1.right and node2.right:
            q1.append(node1.right)
            q2.append(node2.right)
        elif node1.right or node2.right:
            return False

    # If both queues are empty, the trees are identical
    return not q1 and not q2

if __name__ == "__main__":

    # Representation of input binary tree 1
    #        1
    #       / \
    #      2   3
    #     /
    #    4
    r1 = Node(1)
    r1.left = Node(2)
    r1.right = Node(3)
    r1.left.left = Node(4)

    # Representation of input binary tree 2
    #        1
    #       / \
    #      2   3
    #     /
    #    4
    r2 = Node(1)
    r2.left = Node(2)
    r2.right = Node(3)
    r2.left.left = Node(4)

    if isIdentical(r1, r2):
        print("true")
    else:
        print("false")

C#

using System;
using System.Collections.Generic;

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

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

public class GFG
{
    public static bool isIdentical(Node r1, Node r2)
    {
        if (r1 == null && r2 == null)
            return true;

        if (r1 == null || r2 == null)
            return false;

        // Use two queues for level order traversal
        Queue<Node> q1 = new Queue<Node>();
        Queue<Node> q2 = new Queue<Node>();
        q1.Enqueue(r1);
        q2.Enqueue(r2);

        while (q1.Count > 0 && q2.Count > 0)
        {
            Node node1 = q1.Dequeue();
            Node node2 = q2.Dequeue();

            // Check if the current nodes are identical
            if (node1.data != node2.data)
                return false;

            // Check the left children
            if (node1.left != null && node2.left != null)
            {
                q1.Enqueue(node1.left);
                q2.Enqueue(node2.left);
            }
            else if (node1.left != null || node2.left != null)
            {
                return false;
            }

            // Check the right children
            if (node1.right != null && node2.right != null)
            {
                q1.Enqueue(node1.right);
                q2.Enqueue(node2.right);
            }
            else if (node1.right != null || node2.right != null)
            {
                return false;
            }
        }

        // If both queues are empty, the trees are identical
        return q1.Count == 0 && q2.Count == 0;
    }

    public static void Main()
    {
        // Representation of input binary tree 1
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r1 = new Node(1);
        r1.left = new Node(2);
        r1.right = new Node(3);
        r1.left.left = new Node(4);

        // Representation of input binary tree 2
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r2 = new Node(1);
        r2.left = new Node(2);
        r2.right = new Node(3);
        r2.left.left = new Node(4);

        if (isIdentical(r1, r2))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

JavaScript

// Node structure
function Node(val) {
    this.data = val;
    this.left = null;
    this.right = null;
}

// Simple Queue class
class Queue {
    constructor() {
        this.items = [];
        this.frontIndex = 0;
    }

    enqueue(item) {
        this.items.push(item);
    }

    dequeue() {
        if (this.frontIndex < this.items.length) {
            return this.items[this.frontIndex++];
        }
        return null;
    }

    isEmpty() {
        return this.frontIndex >= this.items.length;
    }
}

function isIdentical(r1, r2) {
    if (r1 === null && r2 === null)
        return true;

    if (r1 === null || r2 === null)
        return false;

    // Use two queues for level order traversal
    let q1 = new Queue();
    let q2 = new Queue();
    q1.enqueue(r1);
    q2.enqueue(r2);

    while (!q1.isEmpty() && !q2.isEmpty()) {
        let node1 = q1.dequeue();
        let node2 = q2.dequeue();

        // Check if the current nodes are identical
        if (node1.data !== node2.data)
            return false;

        // Check the left children
        if (node1.left && node2.left) {
            q1.enqueue(node1.left);
            q2.enqueue(node2.left);
        } else if (node1.left || node2.left) {
            return false;
        }

        // Check the right children
        if (node1.right && node2.right) {
            q1.enqueue(node1.right);
            q2.enqueue(node2.right);
        } else if (node1.right || node2.right) {
            return false;
        }
    }

    // If both queues are empty, the trees are identical
    return q1.isEmpty() && q2.isEmpty();
}

// Driver code

// Representation of input binary tree 1
//        1
//       / \
//      2   3
//     / 
//    4
let r1 = new Node(1);
r1.left = new Node(2);
r1.right = new Node(3);
r1.left.left = new Node(4);

// Representation of input binary tree 2
//        1
//       / \
//      2   3
//     / 
//    4
let r2 = new Node(1);
r2.left = new Node(2);
r2.right = new Node(3);
r2.left.left = new Node(4);

if (isIdentical(r1, r2))
    console.log("true");
else
    console.log("false");

Output

true

Time complexity: O(n), where n is the number of nodes in the larger of the two trees, as each node is visited once.
Auxiliary Space: O(w), where w is the maximum width of the trees at any level, due to the space required for the queues.

[Expected Approach] Using Morris Traversal

Traverse both trees simultaneously using Morris traversal, comparing node values and structure without recursion or stacks. Temporary links are used to navigate subtrees efficiently, and all links are removed after traversal.

Steps:

Start at the root of both trees.
If a node has a left child, go to its left subtree and find the rightmost node there; temporarily link it back to the current node.
Move to the left child; if no left child, compare the nodes of both trees.
After left subtree, follow the temporary link back, then go to the right child.
If any node mismatch or missing node is found, return false.
Remove all temporary links.
Continue until all nodes are visited; if all match, return true.

C++

#include <iostream>
using namespace std;

// Node structure
class Node {
public:
    int data;
    Node *left, *right;

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

bool isIdentical(Node* r1, Node* r2) {

    if (r1 == nullptr && r2 == nullptr)
        return true;
        
    if (r1 == nullptr || r2 == nullptr)
        return false;

    while (r1 != nullptr && r2 != nullptr) {

        if (r1->data != r2->data)
            return false;

        // Morris traversal for the first tree (r1)
        if (r1->left == nullptr) {
            
            // Move to the right child if no left child
            r1 = r1->right;
        } else {
            
            // Find the inorder predecessor of r1
            Node* pre = r1->left;
            while (pre->right != nullptr
                && pre->right != r1) {
                pre = pre->right;
            }

            // Set the temporary link to r1
            if (pre->right == nullptr) {
                pre->right = r1;
                r1 = r1->left;
            } 
          
            // Remove the temporary link and move to right
            else {
                pre->right = nullptr;
                r1 = r1->right;
            }
        }

        // Morris traversal for the second tree (r2)
        if (r2->left == nullptr) {
            
            // Move to the right child if no left child
            r2 = r2->right;
        } else {
            
            // Find the inorder predecessor of r2
            Node* pre = r2->left;
            while (pre->right != nullptr
                && pre->right != r2) {
                pre = pre->right;
            }

            // Set the temporary link to r2
            if (pre->right == nullptr) {
                pre->right = r2;
                r2 = r2->left;
            } 
          
            // Remove the temporary link and move to right
            else {
                pre->right = nullptr;
                r2 = r2->right;
            }
        }
    }

    return (r1 == nullptr && r2 == nullptr);
}

int main() {

    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r1 = new Node(1);
    r1->left = new Node(2);
    r1->right = new Node(3);
    r1->left->left = new Node(4);

    // Representation of input binary tree 2
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    Node* r2 = new Node(1);
    r2->left = new Node(2);
    r2->right = new Node(3);
    r2->left->left = new Node(4);

    if (isIdentical(r1, r2))
        cout << "true\n";
    else
        cout << "false\n";

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int x) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int isIdentical(struct Node* r1, struct Node* r2) {

    if (r1 == NULL && r2 == NULL)
        return 1;

    if (r1 == NULL || r2 == NULL)
        return 0;

    while (r1 != NULL && r2 != NULL) {

        if (r1->data != r2->data)
            return 0;

        // Morris traversal for the first tree (r1)
        if (r1->left == NULL) {

            // Move to the right child if no left child
            r1 = r1->right;
        } else {

            // Find the inorder predecessor of r1
            struct Node* pre = r1->left;
            while (pre->right != NULL && pre->right != r1) {
                pre = pre->right;
            }

            // Set the temporary link to r1
            if (pre->right == NULL) {
                pre->right = r1;
                r1 = r1->left;
            }

            // Remove the temporary link and move to right
            else {
                pre->right = NULL;
                r1 = r1->right;
            }
        }

        // Morris traversal for the second tree (r2)
        if (r2->left == NULL) {

            // Move to the right child if no left child
            r2 = r2->right;
        } else {

            // Find the inorder predecessor of r2
            struct Node* pre = r2->left;
            while (pre->right != NULL && pre->right != r2) {
                pre = pre->right;
            }

            // Set the temporary link to r2
            if (pre->right == NULL) {
                pre->right = r2;
                r2 = r2->left;
            }

            // Remove the temporary link and move to right
            else {
                pre->right = NULL;
                r2 = r2->right;
            }
        }
    }

    return (r1 == NULL && r2 == NULL);
}

int main() {

    // Representation of input binary tree 1
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    struct Node* r1 = newNode(1);
    r1->left = newNode(2);
    r1->right = newNode(3);
    r1->left->left = newNode(4);

    // Representation of input binary tree 2
    //        1
    //       / \
    //      2   3
    //     /
    //    4
    struct Node* r2 = newNode(1);
    r2->left = newNode(2);
    r2->right = newNode(3);
    r2->left->left = newNode(4);

    if (isIdentical(r1, r2))
        printf("true\n");
    else
        printf("false\n");

    return 0;
}

Java

//Node Structure
class Node {
    int data;
    Node left, right;

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

class GFG {

    static boolean isIdentical(Node r1, Node r2) {

        if (r1 == null && r2 == null)
            return true;

        if (r1 == null || r2 == null)
            return false;

        while (r1 != null && r2 != null) {

            if (r1.data != r2.data)
                return false;

            // Morris traversal for the first tree (r1)
            if (r1.left == null) {

                // Move to the right child if no left child
                r1 = r1.right;
            } else {

                // Find the inorder predecessor of r1
                Node pre = r1.left;
                while (pre.right != null && pre.right != r1) {
                    pre = pre.right;
                }

                // Set the temporary link to r1
                if (pre.right == null) {
                    pre.right = r1;
                    r1 = r1.left;
                }

                // Remove the temporary link and move to right
                else {
                    pre.right = null;
                    r1 = r1.right;
                }
            }

            // Morris traversal for the second tree (r2)
            if (r2.left == null) {

                // Move to the right child if no left child
                r2 = r2.right;
            } else {

                // Find the inorder predecessor of r2
                Node pre = r2.left;
                while (pre.right != null && pre.right != r2) {
                    pre = pre.right;
                }

                // Set the temporary link to r2
                if (pre.right == null) {
                    pre.right = r2;
                    r2 = r2.left;
                }

                // Remove the temporary link and move to right
                else {
                    pre.right = null;
                    r2 = r2.right;
                }
            }
        }

        return (r1 == null && r2 == null);
    }

    public static void main(String[] args) {

        // Representation of input binary tree 1
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r1 = new Node(1);
        r1.left = new Node(2);
        r1.right = new Node(3);
        r1.left.left = new Node(4);

        // Representation of input binary tree 2
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r2 = new Node(1);
        r2.left = new Node(2);
        r2.right = new Node(3);
        r2.left.left = new Node(4);

        if (isIdentical(r1, r2))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

#Node Structure
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def isIdentical(r1, r2):

    if r1 is None and r2 is None:
        return True

    if r1 is None or r2 is None:
        return False

    while r1 is not None and r2 is not None:

        if r1.data != r2.data:
            return False

        # Morris traversal for the first tree (r1)
        if r1.left is None:

            # Move to the right child if no left child
            r1 = r1.right
        else:

            # Find the inorder predecessor of r1
            pre = r1.left
            while pre.right is not None and pre.right != r1:
                pre = pre.right

            # Set the temporary link to r1
            if pre.right is None:
                pre.right = r1
                r1 = r1.left

            # Remove the temporary link and move to right
            else:
                pre.right = None
                r1 = r1.right

        # Morris traversal for the second tree (r2)
        if r2.left is None:

            # Move to the right child if no left child
            r2 = r2.right
        else:

            # Find the inorder predecessor of r2
            pre = r2.left
            while pre.right is not None and pre.right != r2:
                pre = pre.right

            # Set the temporary link to r2
            if pre.right is None:
                pre.right = r2
                r2 = r2.left

            # Remove the temporary link and move to right
            else:
                pre.right = None
                r2 = r2.right

    return r1 is None and r2 is None

if __name__ == "__main__":

    # Representation of input binary tree 1
    #        1
    #       / \
    #      2   3
    #     /
    #    4
    r1 = Node(1)
    r1.left = Node(2)
    r1.right = Node(3)
    r1.left.left = Node(4)

    # Representation of input binary tree 2
    #        1
    #       / \
    #      2   3
    #     /
    #    4
    r2 = Node(1)
    r2.left = Node(2)
    r2.right = Node(3)
    r2.left.left = Node(4)

    if isIdentical(r1, r2):
        print("true")
    else:
        print("false")

C#

using System;

//Node Structure
class Node {
    public int data;
    public Node left, right;
    public Node(int v) {
        data = v;
        left = right = null;
    }
}

class GFG {
    public static bool isIdentical(Node r1, Node r2) {

        if (r1 == null && r2 == null)
            return true;

        if (r1 == null || r2 == null)
            return false;

        while (r1 != null && r2 != null) {

            if (r1.data != r2.data)
                return false;

            // Morris traversal for the first tree (r1)
            if (r1.left == null) {

                // Move to the right child if no left child
                r1 = r1.right;
            } else {

                // Find the inorder predecessor of r1
                Node pre = r1.left;
                while (pre.right != null && pre.right != r1) {
                    pre = pre.right;
                }

                // Set the temporary link to r1
                if (pre.right == null) {
                    pre.right = r1;
                    r1 = r1.left;
                }

                // Remove the temporary link and move to right
                else {
                    pre.right = null;
                    r1 = r1.right;
                }
            }

            // Morris traversal for the second tree (r2)
            if (r2.left == null) {

                // Move to the right child if no left child
                r2 = r2.right;
            } else {

                // Find the inorder predecessor of r2
                Node pre = r2.left;
                while (pre.right != null && pre.right != r2) {
                    pre = pre.right;
                }

                // Set the temporary link to r2
                if (pre.right == null) {
                    pre.right = r2;
                    r2 = r2.left;
                }

                // Remove the temporary link and move to right
                else {
                    pre.right = null;
                    r2 = r2.right;
                }
            }
        }

        return r1 == null && r2 == null;
    }

    static void Main() {

        // Representation of input binary tree 1
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r1 = new Node(1);
        r1.left = new Node(2);
        r1.right = new Node(3);
        r1.left.left = new Node(4);

        // Representation of input binary tree 2
        //        1
        //       / \
        //      2   3
        //     /
        //    4
        Node r2 = new Node(1);
        r2.left = new Node(2);
        r2.right = new Node(3);
        r2.left.left = new Node(4);

        if (isIdentical(r1, r2))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

JavaScript

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

function isIdentical(r1, r2) {

    if (r1 === null && r2 === null)
        return true;

    if (r1 === null || r2 === null)
        return false;

    while (r1 !== null && r2 !== null) {

        if (r1.data !== r2.data)
            return false;

        // Morris traversal for the first tree (r1)
        if (r1.left === null) {

            // Move to the right child if no left child
            r1 = r1.right;
        } else {

            // Find the inorder predecessor of r1
            let pre = r1.left;
            while (pre.right !== null && pre.right !== r1) {
                pre = pre.right;
            }

            // Set the temporary link to r1
            if (pre.right === null) {
                pre.right = r1;
                r1 = r1.left;
            }

            // Remove the temporary link and move to right
            else {
                pre.right = null;
                r1 = r1.right;
            }
        }

        // Morris traversal for the second tree (r2)
        if (r2.left === null) {

            // Move to the right child if no left child
            r2 = r2.right;
        } else {

            // Find the inorder predecessor of r2
            let pre = r2.left;
            while (pre.right !== null && pre.right !== r2) {
                pre = pre.right;
            }

            // Set the temporary link to r2
            if (pre.right === null) {
                pre.right = r2;
                r2 = r2.left;
            }

            // Remove the temporary link and move to right
            else {
                pre.right = null;
                r2 = r2.right;
            }
        }
    }

    return (r1 === null && r2 === null);
}

// Driver code

// Representation of input binary tree 1
//        1
//       / \
//      2   3
//     /
//    4
let r1 = new Node(1);
r1.left = new Node(2);
r1.right = new Node(3);
r1.left.left = new Node(4);

// Representation of input binary tree 2
//        1
//       / \
//      2   3
//     /
//    4
let r2 = new Node(1);
r2.left = new Node(2);
r2.right = new Node(3);
r2.left.left = new Node(4);

if (isIdentical(r1, r2))
    console.log("true");
else
    console.log("false");

Output

true

Time Complexity: O(n), where n is the number of nodes in the larger of the two trees, as each node is visited once.
Auxiliary Space: O(1), modifying tree temporarily by establishing "threads" to traverse nodes without using recursion or a stack.

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem