How to Determine if Two Binary Trees are Identical

Introduction

In computer science, binary trees are fundamental data structures used in various applications, including searching and sorting. One common problem is determining whether two binary trees are identical. Two binary trees are considered identical if they have the same structure and their corresponding nodes have the same values. In this article, we will learn how to determine if two binary trees are Identical.

Problem Statement

Given two binary trees, the goal is to check whether they are structurally identical and contain the same data in corresponding nodes. This means every node in the first tree must match the corresponding node in the second tree in both position and value.

Approach

To solve this problem, we can use recursion. The idea is to compare the root nodes of both trees and then recursively check the left and right subtrees. The base cases will handle situations where either of the nodes is null. Specifically:

• If both nodes are null, they are considered identical at that position.
• If only one of them is null, the trees are not identical.
• If both nodes are not null, compare their values and recursively check their left and right children.

Java Implementation

Below is an implementation in Java that demonstrates this approach:

public class IdenticalBinaryTrees {

	class BinTreeNode {
	    int val;
	    BinTreeNode left;
	    BinTreeNode right;

	    BinTreeNode(int x) {
	        val = x;
	    }
	}
	
    public static boolean areIdentical(BinTreeNode first, BinTreeNode second) {
        if (first == null && second == null) {
            return true;
        }

        if (first == null || second == null) {
            return false;
        }

        if (first.val != second.val) {
            return false;
        }

        return areIdentical(first.left, second.left) && areIdentical(first.right, second.right);
    }

    public static void main(String[] args) {
        BinTreeNode binTreeNode = new IdenticalBinaryTrees().new BinTreeNode(1);
        binTreeNode.left = new IdenticalBinaryTrees().new BinTreeNode(2);
        binTreeNode.right = new IdenticalBinaryTrees().new BinTreeNode(3);

        BinTreeNode tree2 = new IdenticalBinaryTrees().new BinTreeNode(1);
        tree2.left = new IdenticalBinaryTrees().new BinTreeNode(2);
        tree2.right = new IdenticalBinaryTrees().new BinTreeNode(3);

        boolean result = areIdentical(binTreeNode, tree2);
        System.out.println("Are the two binary trees identical? " + result);
    }
}

Example Explanation

In the main method, we construct two binary trees:

• Tree 1: Root node with value 1, left child with value 2, and right child with value 3
• Tree 2: Structured identically to Tree 1, with the same node values

When we call the areIdentical method with these trees, the method will return true, indicating that the two trees are indeed identical.

Conclusion

Checking whether two binary trees are identical is a classic recursive problem that tests both structural and data equality. With a simple recursive method, we can efficiently compare trees of any size. This technique is fundamental in many real-world applications, such as comparing XML documents, file system structures, and more.

You can find the example code on Github.