Check if a Binary Tree contains duplicate subtrees of size 2 or more | Javascript 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
let MARKER = ' ' ; class Node { constructor ( data ) { this . data = data ; } } function dupSubUtil ( root , subtrees ) { let s = " " ; if ( root == null ) return s + MARKER ; let lStr = dupSubUtil ( root . left , subtrees ) ; if ( lStr == ( s ) ) return s ; let rStr = dupSubUtil ( root . right , subtrees ) ; if ( rStr == ( s ) ) return s ; s = s + root . data + lStr + rStr ; if ( s . length > 3 && subtrees . has ( s ) ) return " " ; subtrees . add ( s ) ; return s ; } function dupSub ( root ) { let subtrees = new Set ( ) ; return dupSubUtil ( root , subtrees ) ; } let root = new Node ( ' ' ) ; root . left = new Node ( ' ' ) ; root . right = new Node ( ' ' ) ; root . left . left = new Node ( ' ' ) ; root . left . right = new Node ( ' ' ) ; root . right . right = new Node ( ' ' ) ; root . right . right . right = new Node ( ' ' ) ; root . right . right . left = new Node ( ' ' ) ; let str = dupSub ( root ) ; if ( str == ( " " ) ) document . write ( " " ) ; else document . write ( " " ) ;