GitHub Account Google Scholar Account LinkedIn Account Twitter Account flickr Account vialab Research Group Profile Page

Determining if Two Trees are Identical

Date: May 21, 2016
The algorithm presented here is suited for trees in general (ie. it works for non-binary trees as well).
import java.util.LinkedList;
import java.util.Iterator;

public class IdenticalTrees {

    public static void main(String[] args) {

        int numNodes = 15;
        Node headOne = new Node(0);
        Node headTwo = new Node(0);

        setupTree(headOne, numNodes);
        setupTree(headTwo, numNodes);

        boolean flag = isIdentical(headOne, headTwo);
        System.out.println("Trees are identical? " + flag);
    }

    public static boolean isIdentical(Node nodeOne, Node nodeTwo) {

        if (nodeOne == null && nodeOne == null) {
            return true;

        } else if (nodeOne == null || nodeTwo == null
            || (nodeOne.children.size() != nodeTwo.children.size())) {

            return false;

        } else if (nodeOne.value == nodeTwo.value) {

            Iterator<Node> iterOne = nodeOne.children.iterator();
            Iterator<Node> iterTwo = nodeTwo.children.iterator();
            boolean flag = true;

            while (iterOne.hasNext()) {

                Node childOne = iterOne.next();
                Node childTwo = iterTwo.next();

                flag = flag && isIdentical(childOne, childTwo);
            }

            return flag;
        }

        return false;
    }

    public static void setupTree(Node head, int numNodes) {

        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(head);

        for (int i = 1; i <= numNodes; i += 2) {

            Node curNode = queue.remove();
            Node leftChild = new Node(i);
            Node rightChild = new Node(i + 1);

            curNode.children.add(leftChild);
            curNode.children.add(rightChild);

            queue.add(leftChild);
            queue.add(rightChild);
        }
    }

    public static class Node {

        LinkedList<Node> children;
        int value;

        public Node(int value) {
            this.value = value;
            children = new LinkedList<Node>();
        }
    }
}