[JOIN HERE] for daily coding insights

DSA SERIES Chapter 26 : CHECK IF TWO BINARY TREES ARE IDENTICAL(C Version)

1. Objective

To determine whether two given binary trees are identical, meaning:

They have the same structure
They contain the same data at corresponding nodes

2. Definition (Exam-Ready)

Two binary trees are said to be identical if both their structure and node values are exactly the same at every corresponding position.

3. Conditions for Identical Trees

Two trees T1 and T2 are identical if and only if:

Both trees are empty
Root values of both trees are equal
Left subtrees are identical
Right subtrees are identical

If any one condition fails, the trees are not identical.

4. Example

Tree 1

        1
       / \
      2   3

Tree 2

        1
       / \
      2   3

✅ Identical Trees

Non-Identical Case

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

❌ Not Identical (structure differs)

5. Key Observation

Tree comparison must be recursive
Iterative comparison is complex and not preferred
Preorder comparison logic fits naturally

6. Recursive Logic

For nodes n1 and n2:

if both nodes are NULL → identical
if one node is NULL → not identical
if data differs → not identical
else:
    check left subtrees
    check right subtrees

7. Structure Definition (Node)

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

8. Function to Check Identical Trees

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

    if (root1 == NULL || root2 == NULL)
        return 0;

    if (root1->data != root2->data)
        return 0;

    return areIdentical(root1->left, root2->left) &&
           areIdentical(root1->right, root2->right);
}

9. Line-by-Line Explanation

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

Both subtrees are empty
Hence identical

if (root1 == NULL || root2 == NULL)
    return 0;

One tree has a node while the other does not
Structures differ

if (root1->data != root2->data)
    return 0;

Node values do not match

return areIdentical(root1->left, root2->left) &&
       areIdentical(root1->right, root2->right);

Recursively compare left and right subtrees
Logical AND ensures both must be identical

10. Complete C Program

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

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

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

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

    if (root1 == NULL || root2 == NULL)
        return 0;

    if (root1->data != root2->data)
        return 0;

    return areIdentical(root1->left, root2->left) &&
           areIdentical(root1->right, root2->right);
}

int main()
{
    struct Node* root1 = createNode(1);
    root1->left = createNode(2);
    root1->right = createNode(3);

    struct Node* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(3);

    if (areIdentical(root1, root2))
        printf("Both trees are IDENTICAL");
    else
        printf("Trees are NOT identical");

    return 0;
}