vendredi 13 mars 2015

Comparing pattern of a haystack and needle [Trees]



I am trying to compare if the pattern starting from a particular node matches as that of the needle. I am just comparing the pattern and do not care about the value stored in the node. My implementation goes as follows -



public static boolean isSubtree(Node haystack, Node needle) {
if (needle == null)// Empty Subtree is accepted
return true;

if (haystack == null)
return false;

return isSubtree(haystack.getLeftChild(), needle.getLeftChild())
&& isSubtree(haystack.getRightChild(), needle.getRightChild());
}


Problem -


For a particular case where I have got :


Haystack - (1,(2,(4),(5)),(3,,(6,(7,,),)))


Needle - (12,(1),(2))


enter image description here


When I try to test it with the cases - My program returns true for



ROOT //correct
ROOT -> Left //correct
ROOT -> Right //Wrong


Whereas as it can be seen, it should just be



ROOT //correct
ROOT -> Left //correct



Aucun commentaire:

Enregistrer un commentaire