CODEWITHSUNDEEP
c++ctree
user2560730
user2560730

Reputation: 345

How to check if a tree is a subtree of another tree?

So, I have the obvious brute-force algorithm, which goes as 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 this is O(n²) approach.

I have another approach which goes as follows and is O(n) We, traverse the first tree in inorder fashion and store it in an array. Then we traverse the second tree and store it in inorder fashion. Now if the second array is a subarray of the first, we go ahead and repeat the same procudure for preorder traversal too. If both the queries result TRUE, The tree is subtree of the first tree. Otherwise, not.

Can somebody tell me whether the following algorithm would work or not?

And is there a more space optimized solution to this problem?

Note: I need two arrays, since I am storing the traversals for both the arrays, is there anyway I could just do with one array? Like I would store the inorder traversal of one of the trees, and then use that array to check for the subarray condition while traversing the other tree. Or maybe no extra space but O(n) time complexity?

Note: By sub-array, I mean that the elements should occur consecutively, i.e

{2,3,5} is a subarray of {1,2,3,5} but not a subarray of {1,2,3,4,5}

Upvotes: 3

Views: 3352

Answers (4)

SliceSort
SliceSort

Reputation: 375

In array {2,3,5}, root can be 2, or 3, or 5, so you can't represent a tree use a array such as this.

If A is subtree of B(similar as your code), and assume leafs(x) is array of "tree x's leaf nodes" from left to right, then leafs(A) is substring of leafs(B).

Once you find a substring as above, check nodes from leaf up to root to ensure it's really a subtree.

Upvotes: 0

Tanu Saxena
Tanu Saxena

Reputation: 779

We can use inorder traversal and DFS( in a binary tree, it reduces to preorder traversal). Now first with DFS, modify the data structure of both the trees and at each node store the no of sub trees under it. After that write the inorder traversal for both the trees and then match the strings with KMP. In O(n+m) (n & m- nodes in both the trees), we can find out the different matchings. We can use hashing to connect to the modified graph with DFS. On each matching with KMP, we can compare the DFS modified graphs of the two (on the no. of subtrees) and if it matches as well for the whole sequence, it is a subtree, else we go for another match of KMP and so on.

In the above ex, the modified data structure fot 'T' after DFS is [x(2);y(0);z(0)] & for 'S' [x(3);y(0);z(1);q(0)]. Inorder for 'T': yxz Inorder for 'S': yxzq

We get the match 'yxz'. Now we go to the DFS modified structure. There is a mismatch at x; So, 'T' is not a subtree of 'S'.

Upvotes: 0

Tony Delroy
Tony Delroy

Reputation: 106106

Summary: consider storing a hash and/or the sub-tree size in each node to speed searches. Your proposed algorithm is broken.

Your proposed algorithm - broken?

If I've understood your proposed alternative algorithm correctly, then it doesn't works. As a 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 are found embedded in S's, despite T not being a valid match (as per your recursive approach).

Quickly eliminating subtrees during a recursive matching process

I'd been thinking along the lines of Karthikeyan's suggestion - store subtree depth at each node, as it lets you elimate a lot of comparisons. Of course, if maintained dynamically it makes certain tree operations more expensive too - have to prioritorise either those or the extra hit during subtree finds.

Storing a hash of subtree elements is another possibility. What makes sense depends how dynamically the tree's structure and data is updated compared to the subtree finds, and whether either is more crucial from an overall perforamnce perspective.

Further reading

Anyway, there are lots of existing questions about this, e.g. Find whether a tree is a subtree of other. Ohhh - found this too - Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings - which seems to support my logic above given you're saying the recursive approach is correct but slow.

Upvotes: 1

Karthikeyan
Karthikeyan

Reputation: 990

What about doing a depth first search and store the number of subtree nodes at every node and compare only the sub trees of parent whose nodes count is equivalent to the other tree under question.

Upvotes: 0

Related Questions