c++ - How to check if a tree is a subtree of another tree? -

so, have obvious brute-force algorithm, goes follows

int issubtree (bintree *s, bintree *t) {     if (s == null)         return 0;     return (isequal (s,t) || issubtree (s->left, t) || issubtree (s->right, t)); }  int isequal (bintree *s, bintree *t) {     if (s==null && t==null)         return 1;     if (s==null || t==null)         return 0;     if (s->val == t->val)         return isequal(s->left,t->left) && isequal (s->right,t->right);     else         return 0; } 

but o(n²) approach.

i have approach goes follows , o(n) we, traverse first tree in inorder fashion , store in array. traverse second tree , store in inorder fashion. if second array subarray of first, go ahead , repeat same procudure preorder traversal too. if both queries result true, tree subtree of first tree. otherwise, not.

can tell me whether following algorithm work or not?

and there more space optimized solution problem?

note: need 2 arrays, since storing traversals both arrays, there anyway 1 array? store inorder traversal of 1 of trees, , use array check subarray condition while traversing other tree. or maybe no space o(n) time complexity?

note: sub-array, mean elements should occur consecutively, i.e

{2,3,5} subarray of {1,2,3,5} not subarray of {1,2,3,4,5} 

summary: consider storing hash and/or sub-tree size in each node speed searches. proposed algorithm broken.

your proposed algorithm - broken?

if i've understood proposed alternative algorithm correctly, doesn't works. counter example, consider:

  t          s   x          x  / \        / \ y   z      y   z                 \                  q 

t has inorder traversal yxz, preorder xyz. s has inorder traversal yxzq, preorder xyzq.

so, t's traversals found embedded in s's, despite t not being valid match (as per recursive approach).

quickly eliminating subtrees during recursive matching process

i'd been thinking along lines of karthikeyan's suggestion - store subtree depth @ each node, lets elimate lot of comparisons. of course, if maintained dynamically makes tree operations more expensive - have prioritorise either or hit during subtree finds.

storing hash of subtree elements possibility. makes sense depends how dynamically tree's structure , data updated compared subtree finds, , whether either more crucial overall perforamnce perspective.

further reading

anyway, there lots of existing questions this, e.g. find whether tree subtree of other. ohhh - found - determine if binary tree subtree of binary tree using pre-order , in-order strings - seems support logic above given you're saying recursive approach correct slow.