CODEWITHSUNDEEP
c++binary-tree
nan
nan

Reputation: 241

Binary trees contained of other binary trees

I have a function that is supposed to tell whether a given binary tree A is contained by a given binary tree B. The function defines "contained" as "A is covered by B, or any complete subtree of B." If, for instance, tree A is an empty tree and tree B is not, would A therefore be contained in B? What about if they're both empty?

Thanks!

Upvotes: 1

Views: 395

Answers (1)

PiotrNycz
PiotrNycz

Reputation: 24347

In mathematic sense empty set (tree is just specialization of set) is contained in every other set including other empty set.

So yes on both your questions.

Empty set has even its wiki: http://en.wikipedia.org/wiki/Empty_set

enter image description here

Anyway it will become obvious from your implementation that the empty tree is contained in every other tree, an example implementation will look like this:

bool Tree::contains(const Tree& otherTree)
{
   for (n: otherTree)
   {
      if (!contains(n)) 
         return false;
   }
   return true;
}

Of course I can imagine better implementation especially when trees are sorted - but the point is that if for(n: otherTree) will cause no iterations then the result is true.

Upvotes: 3

Related Questions