Check if a Binary Tree contains duplicate subtrees of size 2 or more | Java program to find if there is a duplicate sub - tree of size 2 or more . ; A binary tree Node has data , pointer to left child and a pointer to right child ; This function returns empty string if tree contains a duplicate subtree of size 2 or more . ; If current node is NULL , return marker ; If left subtree has a duplicate subtree . ; Do same for right subtree ; Serialize current subtree ; If current subtree already exists in hash table . [ Note that size of a serialized tree with single node is 3 as it has two marker nodes . ; Function to find if the Binary Tree contains duplicate subtrees of size 2 or more ; Driver program to test above functions
import java . util . HashSet ; public class Main { static char MARKER = ' $ ' ; class Node { int data ; Node left , right ; Node ( int data ) { this . data = data ; } } ; public static String dupSubUtil ( Node root , HashSet < String > subtrees ) { String s = " " ; if ( root == null ) return s + MARKER ; String lStr = dupSubUtil ( root . left , subtrees ) ; if ( lStr . equals ( s ) ) return s ; String rStr = dupSubUtil ( root . right , subtrees ) ; if ( rStr . equals ( s ) ) return s ; s = s + root . data + lStr + rStr ; if ( s . length ( ) > 3 && subtrees . contains ( s ) ) return " " ; subtrees . add ( s ) ; return s ; } public static String dupSub ( Node root ) { HashSet < String > subtrees = new HashSet < > ( ) ; return dupSubUtil ( root , subtrees ) ; } public static void main ( String args [ ] ) { Node root = new Node ( ' A ' ) ; root . left = new Node ( ' B ' ) ; root . right = new Node ( ' C ' ) ; root . left . left = new Node ( ' D ' ) ; root . left . right = new Node ( ' E ' ) ; root . right . right = new Node ( ' B ' ) ; root . right . right . right = new Node ( ' E ' ) ; root . right . right . left = new Node ( ' D ' ) ; String str = dupSub ( root ) ; if ( str . equals ( " " ) ) System . out . print ( " ▁ Yes ▁ " ) ; else System . out . print ( " ▁ No ▁ " ) ; } }