Duplicate Sub Trees – AlgoBox by dietpepsi
Find if a given tree has duplicate subtrees or not. Leaves do not count as subtrees.
Solution
The original post states that “two leaf nodes of a parent do not count as subtree”.
I believe that it means “leaves do not count as subtrees”. Because if leaves count as subtrees, for a tree to have no duplicate subtrees, all the leaves must have unique values. And if all leaves have unique values then no matter how two subtrees are same in structure, they can not be the same since they have different leaves. Therefore, the problem is equivalent to “find if a given tree has duplicate leaves or not”, which is trivial.
If two subtrees are the same, they must have the same height. Thus, we can traversal the tree in the reverse level order (from leaves to root).
At level h, suppose we try to compare two subtrees with root nodes node[i] and node[j]. Then we just need to compare that node[i].val == node[j].val and isSame(node[i].left, node[j].left) and isSame(node[i].right, node[j].right). And since we have compared and memoized level h-1, the two recursive calls is O(1) time.
However, we then find the issue with the problem statement. Like the previous prove about the leaves which is just level 1. If there are no duplicate subtrees at level h, then there will be no duplicate subtrees at level h+1. Therefore the problem then equivalent to “find if a given tree has duplicate high two subtrees or not.”
Thus, I think the problem should be “find the largest duplicate subtree in a tree” or “find if a tree has duplicate subtrees of height h“.
Read full article from Duplicate Sub Trees – AlgoBox by dietpepsi
