Check if a binary tree has two identical subtrees

Question

I want to write a method to find whether a tree has at least a pair of identical subtrees, the subtrees have to be identical in both value and structure.

Suppose you are given a tree as follows:

        a
       / \
      b   f
     /   / \
    c   g   d
   /   /   /
  d   h   e
 /
e

This would return true because we have a pair of identical trees with root d.

My thought is to traverse each node and build a map of node name mapped to list of tree nodes. In each iteration, we check if current node name is in the map or not. If it's in, then we can call boolean isSameTree(TreeNode t1, TreeNode t2) function with current node against every node in the list of tree nodes to see if they are identical.

The time complexity would be O(n^3). And I wonder if we can do better than that!

Answer 1

Your example tree also has a pair of identical trees with root e. In general, if two trees are identical then either they are both leaves or they have subtrees which are identical. So you can simplify your test to checking whether all of the leaves in the original tree are distinct, which takes O(n) hashing operations and average case Theta(n) equality comparisons unless the hash is very poor.