Check if two trees are identical or not

You are given two binary trees. The task is to check whether the two trees are identical or not. Two binary trees are considered identical if they have the same structure, and the corresponding nodes have the same values.

Input/Output Examples

Example 1:

Input:

plaintext

Output: True
- Explanation: Both trees have the same structure and values at corresponding nodes, so they are identical.

Example 2:

Input:

plaintext

Output: False
- Explanation: The structure is the same, but the values at the corresponding nodes (3 and 4) are different, so the trees are not identical.

Approach to check if two trees are identical or not

Recursive Approach:
- For two trees to be identical, the following conditions must be true:
  - The current nodes of both trees must have the same value.
  - The left subtree of the first tree must be identical to the left subtree of the second tree.
  - The right subtree of the first tree must be identical to the right subtree of the second tree.
Base Case:
- If both nodes are None, the trees are identical (empty trees).
- If one node is None and the other is not, the trees are not identical.
Recursive Check:
- Recursively compare the left and right subtrees of both trees to determine if they are identical.

C++ Program to check if two trees are identical or not

cpp

#include <iostream>
using namespace std;

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

// Function to check if two trees are identical
bool areIdentical(Node* root1, Node* root2) {
    // If both trees are empty
    if (root1 == NULL && root2 == NULL) {
        return true;
    }

    // If both nodes are not NULL, check if the data is the same and
    // recursively check for left and right subtrees
    if (root1 != NULL && root2 != NULL) {
        return (root1->data == root2->data) &&
               areIdentical(root1->left, root2->left) &&
               areIdentical(root1->right, root2->right);
    }

    // One tree is empty, and the other is not
    return false;
}

int main() {
    Node* root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    
    Node* root2 = new Node(1);
    root2->left = new Node(2);
    root2->right = new Node(3);
    
    if (areIdentical(root1, root2)) {
        cout << "The trees are identical." << endl;
    } else {
        cout << "The trees are not identical." << endl;
    }
    
    return 0;
}

Java Program to check if two trees are identical or not

java

// A binary tree node class
class Node {
    int data;
    Node left, right;
    
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    // Function to check if two trees are identical
    public boolean areIdentical(Node root1, Node root2) {
        // If both trees are empty
        if (root1 == null && root2 == null) {
            return true;
        }

        // If both nodes are not null, check if the data is the same
        // and recursively check for left and right subtrees
        if (root1 != null && root2 != null) {
            return (root1.data == root2.data) &&
                   areIdentical(root1.left, root2.left) &&
                   areIdentical(root1.right, root2.right);
        }

        // One tree is empty, and the other is not
        return false;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        
        if (tree.areIdentical(root1, root2)) {
            System.out.println("The trees are identical.");
        } else {
            System.out.println("The trees are not identical.");
        }
    }
}

Python Program to check if two trees are identical or not

python

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

# Function to check if two trees are identical
def are_identical(root1, root2):
    # If both trees are empty
    if root1 is None and root2 is None:
        return True

    # If both nodes are not None, check if the data is the same
    # and recursively check for left and right subtrees
    if root1 is not None and root2 is not None:
        return (root1.data == root2.data and
                are_identical(root1.left, root2.left) and
                are_identical(root1.right, root2.right))
    
    # One tree is empty, and the other is not
    return False

# Example usage
if __name__ == "__main__":
    root1 = Node(1)
    root1.left = Node(2)
    root1.right = Node(3)
    
    root2 = Node(1)
    root2.left = Node(2)
    root2.right = Node(3)
    
    if are_identical(root1, root2):
        print("The trees are identical.")
    else:
        print("The trees are not identical.")

Explanation of Code:

Base Case:
- If both trees are empty (None), they are identical.
- If only one of the trees is empty and the other is not, they are not identical.
Recursive Case:
- If both nodes are not None, check if the values of the current nodes are the same.
- Recursively check the left and right subtrees of both trees.
Return Value: If all corresponding nodes and their subtrees are identical, the function returns True; otherwise, it returns False.

Time Complexity:

O(n): The function visits each node of both trees exactly once, where n is the number of nodes in the smaller tree.

Space Complexity:

O(h): The space complexity depends on the height of the trees due to the recursive function calls. In the worst case, the space complexity is O(n) when the tree is skewed, and in the best case (for a balanced tree), it is O(log n).