Does a binary tree contain another tree?

Question

Alright guys, I was asked this question in an interview today and it goes like this:

"Tell if one binary tree is contained inside another binary tree or not (contains implies both in structure and value of nodes)"

I thought of the following approach:

Flatten the larger tree as:

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}

(I did actually write code for this, {-} implies empty left or right sub-tree, each sub-tree is enclosed within {} paranthesis)

Now for smaller sub-tree we need to match this pattern:

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}

where {.*} denotes an empty or non-empty sub-tree.

At the time I thought, this will be a trivial regex pattern matching problem in java but I am bamboozled. Actually now I feel, I have just transformed the problem (created one monster out of another).

Is there a simple regex one liner to match these patterns? I understand there might be other approaches to solve this problem and this might not be the best one. I just wonder if this is solvable.

Answer 1

I'm not sure what the interviewer meant exactly by "contained inside another binary tree". If the interviewer was asking for a method to check whether A was a subtree of B, here is one method that does not require regex at all:

• Flatten the trees A and B using preorder traversal to get strings, say, preA and preB
• Flatten the trees A and B using inorder traversal to get strings, say, inA and inB
• Make sure to include the null leaves in the strings as well (using whitespaces for example)
• Check if preA is a substring of preB AND inA is a substring of inB

The reason you wanna include the null leaves is because when multiple nodes have the same value, the preorder and inorder may not be enough. Here is an example:

          A
      A       A
   B     B       C
 C         D       B
D           C       D 

You can also check this out:

checking subtrees using preorder and inorder strings

Also read this for more info on preorder and inorder traversals of binary trees:

http://en.wikipedia.org/wiki/Tree_traversal

Now, if he DIDN'T mean just subtrees, the problem may become more complicated depending on what the interviewer meant by a "part". You could look at the question as a subgraph isomorphism problem (trees are just a subset of graphs) and this is NP-complete.

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

There may be better approaches since trees are much more restricted and simpler than graphs.