Trees

Identical Binary Trees (Same Tree) problem

Rajeev SinghAlgorithms1 mins read

Identical Binary Trees

Identical Binary Trees (Same Tree) 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

Identical Binary Trees (Same Tree) problem solution in Java

The problem can be solved easily using recursion. Two binary trees are identical if:

  • their root nodes have the same value,
  • their left subtree is identical,
  • their right subtree is identical.

Here is the complete solution in Java:

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

class SameTree {
  private static boolean isSameTree(TreeNode a, TreeNode b) {
    if (a == null && b == null) {
      return true;
    }

    if (a == null || b == null) {
      return false;
    }

    return a.val == b.val && 
    isSameTree(a.left, b.left) && 
    isSameTree(a.right, b.right);
  }

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

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

    System.out.println(isSameTree(a, b));
  }
}