I'll point out that if you are building a system where this problem actually occurs (as in generating DAGs in a compiler expression optimizer), you can nearly always engineer the problem down to O(log(| T|)) if T is balanced and O(|T|) in the worst case.
Trees need parent pointers, and also a map must be maintained HashMap<Triple<Node, Node, Data>, Node> nodeMap; where the key holds the children and data value of the corresponding node that has already been generated. The system never constructs a new node without first checking this global map to see if a node with the right pair of children and data has already been generated. If so, the existing node is used. Otherwise a new one is created and added to the map. Now within this system, checking tree equality is the same as checking root pointer equality. (Proof is by induction over the height of trees!) So two trees can be compared in one machine instruction. For the subtree test, just follow parent pointers from S to its root checking each node to see if it's the root of T. On Mar 20, 8:24 am, Dheeraj Sharma <dheerajsharma1...@gmail.com> wrote: > How to check if one binary tree is a sub tree of other? > Any Solution other then bruteforce? > Prototype > bool check(node *t1,node *subtree) > > -- > Sent from my mobile device > > *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
