How to determine if two trees are identical

Problem statement

Given the roots of two binary trees, determine whether or not two binary trees are identical. Identical trees have the same structure and information at every node.

Check the following slides for examples:

1 of 2

Solution

Let’s name the two trees X and Y.

The solution is to use depth first search traversal. We can recursively solve this problem.

The base case is when both or either one of the nodes of the two trees is null.

We can say X and Y are identical when the following conditions are satisfied:

  1. The root node of X and Y have the same data or the roots are pointing to null.
  2. The left subtree of X is identical to the left subtree of Y.
  3. The right subtree of X is identical to the right subtree of Y.

Code example

Let’s look at the code below:

class Main{
    static class Node {
        int data;
        Node left, right;
        Node(int item) {
            data = item;
            left = right = null;
        }
    }
    private Node xroot, yroot;
    boolean areTreesIdentical(Node xroot, Node yroot) {
        if (xroot == null && yroot == null) return true;
        if (xroot != null && yroot != null) {
            return ((xroot.data == yroot.data) &&
                    areTreesIdentical(xroot.left, yroot.left) &&
                    areTreesIdentical(xroot.right, yroot.right));
        }
        return false;
    }
    public static void main(String[] args) {
        Main main = new Main();
        main.xroot = new Node(1);
        main.xroot.left = new Node(2);
        main.xroot.right = new Node(3);
        main.xroot.left.left = new Node(2);
        main.xroot.left.right = new Node(2);
        main.yroot = new Node(1);
        main.yroot.left = new Node(2);
        main.yroot.right = new Node(3);
        main.yroot.left.left = new Node(2);
        System.out.println(main.areTreesIdentical(main.xroot, main.yroot)?"Trees are identical": "Trees are not identical");
    }
}

Code explanation

  • Lines 3 to 11: We define a Node class that consists of data, left node, and right node.
  • Line 13: We declare the root of tree X is xroot and the root of tree Y is yroot.
  • Lines 15 to 26: We define the areTreesIdentical method that accepts the roots of the two trees as arguments. We check whether the current node data is equal and then recursively check for the left and right subtrees of X and Y.
  • Lines 31 to 40: We construct tree X and tree Y.
  • Line 42: We invoke the areTreesIdentical() method with the roots of X and Y.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)