5
\$\begingroup\$

Given two binary trees, you have to find whether the second is a sub tree of the first.

First attempt (brute force):

int issubtree(tree *tree1p, tree * tree2p)
{
    if (tree2p == NULL)
        return 1;

    if (tree1p == NULL)
        return 0;

    if (tree1p->data == tree2p->data)
        return (issubtree(tree1p->leftp,tree2p->leftp) 
                && (issubtree(tree1p->leftp,tree2p->leftp));
    else
        return (issubtree(tree1p->leftp,tree2p) || (issubtree(tree1p->rightp,tree2p));
}

Please give feedback on correctness more efficient code.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'd come up with better (subjective, I know) names for the parameters: int issubtree(const tree *haystack, const tree *needle) \$\endgroup\$
    – pmg
    May 29, 2011 at 14:56
  • \$\begingroup\$ Why cant we get the list of preorder and inorder of both the trees and compare the preorder and inorder of 2 is a subseq of preorder and inorder of 1 \$\endgroup\$
    – user6794
    Aug 31, 2011 at 16:57

2 Answers 2

8
\$\begingroup\$

Firstly, what's will all the p's? I guess they mean pointer? They are silly, get rid of them.

Consider these trees:

     [A]                     [A]
    /   \                   /  \
  [B]   [C]               [D]   [C]
 /
[D]

Your code will claim that the second tree is a subtree of the first. The problem is that you cannot check the left/right matching using issubtree because they need to be exact matches not subtrees. You need to seperate the subtree search from the matching:

int matches(tree * tree1, tree * tree2)
{
    if(tree1 == tree2) return 1;
    if(tree1 == NULL || tree2 == NULL) return 0;
    if(tree1->data != tree2->data) return 0;
    return matches(tree1->left, tree2->left) && matches(tree1->right, tree2->right);
}

int issubtree(tree *haystack, tree * needle)
{
    if(tree1 == haystack) return 0;
    if( matches(haystack, needle) ) return 1;
    return issubtree(haystack->left, tree2) || issubtree(haystack->right, needle);
}

For increased efficiency, we can look at the problem in another way. We can express a tree by its pre-order traversal. So for the first tree above we have:

A,B,D,(NULL),(NULL),(NULL),C,(NULL), (NULL)

We can reconstruct the original tree from this sequence. Additionally, a subtree will show up as a substring of this sequence. This means that we can view the subtree problem as the same as the substring search problem. That's a well studied problem and you can view various algorithms for it here: http://en.wikipedia.org/wiki/String_searching_algorithm

\$\endgroup\$
5
  • \$\begingroup\$ When looking at the wikipedia example for pre-order en.wikipedia.org/wiki/Tree_traversal#Pre-order you can not match sub-tree F,A,B,D,G as substring because C and E are in between. \$\endgroup\$
    – Flip
    Dec 2, 2013 at 21:12
  • \$\begingroup\$ @Flip, that's not a subtree. From wiki: "A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T" C & E have to be included for it to be a subtree. \$\endgroup\$ Dec 3, 2013 at 3:24
  • \$\begingroup\$ I tested mentioned code with your example, but it gives me correct answer. Am I missing something? Code: ideone.com/GLt7za \$\endgroup\$
    – Hengameh
    Aug 24, 2015 at 13:37
  • \$\begingroup\$ @Hengameh, you inputted the tree incorrectly, you swapped left and right in the first tree. \$\endgroup\$ Aug 24, 2015 at 14:07
  • \$\begingroup\$ You are right! Embarrassing! Sorry. \$\endgroup\$
    – Hengameh
    Aug 24, 2015 at 14:35
0
\$\begingroup\$

This algorithm requires the values to maintain the same structure in both trees which is probably okay for this assignment (homework?).

If these are binary search trees, there's at least one optimization you can make right off the bat: inside the else block you don't have to check both directions. Think about how you would find the root node of the subtree in the main tree.

And yes, choosing meaningful variable and function names and using consistent formatting (I fixed it) goes a long way toward keeping code readable.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.