Identical Binary Trees (Same Tree) Problem - Java Solution

1. Introduction

In this blog post, we'll explore a fundamental problem in binary tree data structures - determining if two binary trees are identical. This problem is known as the "Identical Binary Trees" or "Same Tree" problem and is a common question in coding interviews to assess understanding of tree traversal and comparison in Java.

Problem

Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

2. Solution Steps

1. If both trees are null, return true.

2. If one of the trees is null or the values of the root nodes are not equal, return false.

3. Recursively check if the left subtree of the first tree is identical to the left subtree of the second tree and the right subtree of the first tree is identical to the right subtree of the second tree.

4. Return the result of the recursive checks.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        TreeNode tree1 = new TreeNode(1);
        tree1.left = new TreeNode(2);
        tree1.right = new TreeNode(3);

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

        System.out.println("Are trees identical: " + isSameTree(tree1, tree2));
    }

    // Method to check if two binary trees are the same
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true; // Both trees are null
        if (p == null || q == null) return false; // One of the trees is null
        if (p.val != q.val) return false; // Values of nodes are not equal

        // Recursively check left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Output:

Are trees identical: true

Explanation:

In the example, both trees have the same structure and node values (1 -> 2 -> 3). 

The method isSameTree checks if both trees are null, indicating they are identical. If only one is null or the root values are different, it returns false. 

Otherwise, it recursively checks the left and right subtrees for equality. The result is true, indicating the trees are identical.