[JOIN HERE] for daily coding insights

DSA Series Chapter 26 – Check if Two Binary Trees are Identical (Python Version)

1. Objective

To check whether two given binary trees are identical, i.e.:

Same structure
Same data at corresponding nodes

2. Definition (Exam-Oriented)

Two binary trees are identical if they have the same shape and same node values at every corresponding position.

3. When Are Two Trees Identical?

Two trees T1 and T2 are identical if:

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

All four conditions must be true.

4. Visual Example

Identical Trees

        10                10
       /  \              /  \
      5   20            5   20

Not Identical

        10                10
       /                    \
      5                     5

5. Why Recursion Is Used

Binary trees are recursive data structures
Each subtree is itself a binary tree
Recursion naturally compares:
- Current node
- Left subtree
- Right subtree

6. Node Structure (Python Class)

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

Explanation

data → stores node value
left → reference to left child
right → reference to right child

7. Logic to Check Identical Trees

Step-by-step logic:

If both nodes are None → identical
If one node is None → not identical
If data differs → not identical
Else:
    compare left subtrees
    compare right subtrees

8. Function to Check Identical Trees

def are_identical(root1, root2):
    if root1 is None and root2 is None:
        return True

    if root1 is None or root2 is None:
        return False

    if root1.data != root2.data:
        return False

    return (are_identical(root1.left, root2.left) and
            are_identical(root1.right, root2.right))

9. Line-by-Line Explanation

if root1 is None and root2 is None:
    return True

Both trees are empty at this position
Hence identical

if root1 is None or root2 is None:
    return False

One tree has a node, the other does not
Structure mismatch

if root1.data != root2.data:
    return False

Node values differ

return (are_identical(root1.left, root2.left) and
        are_identical(root1.right, root2.right))

Recursively compare:
- Left subtrees
- Right subtrees
and ensures both must match

10. Complete Python Program

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

def are_identical(root1, root2):
    if root1 is None and root2 is None:
        return True

    if root1 is None or root2 is None:
        return False

    if root1.data != root2.data:
        return False

    return (are_identical(root1.left, root2.left) and
            are_identical(root1.right, root2.right))

# -------- 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("Both trees are IDENTICAL")
else:
    print("Trees are NOT identical")