Given two binary trees T1 and T2. Find if T2 is a sub-tree of T1.

Question

rkt · Accepted Answer

int isSubTree(struct node *T1, struct node *T2){
        if(T2 == NULL) return 1;           // NULL tree is subtree of any tree
        else if(T1 == NULL) return 0;  // if T2 is not NULL and T1 is NULL
        else if(T1 == T2) return 1;        // if T1 and T2 both equal and not equal to NULL
        else return isSubTree(T1->left, T2) || isSubTree(T1->right, T2);
}

Sigiloso · Answer

This is what I would do (pseudo code):

bool isSubtree(BinaryTree* T1, BinaryTree* T2) {
     if(T1 == T2) {
          return true;
     }

    if (!T1.hasChildren()) {
        return false;
    }

    return isSubtree(T1.left, T2) || isSubtree(T1.right, T2);
}

Saranya · Answer

Here what we are essentially doing is comparing the pointer values - is that what is expected? Or is it that return true if T2 is a subtree of T1 according to its values? Which means that if T2 has completely different pointers, but still has the same values as some subtree of T1, then we should return true, else false.

Gliss · Answer

@Saranya: No we're looking at the node values. Otherwise it would be far too simple (since if the object is the same at the first level, it garantees that children are too, and so one...)

Sigiloso · Answer

The first solution lacks T1==null checking. rkt's solution is perfect. The comments by the 'Anonymous April 8 2012' and the negative sign for the first answer is definitely posted by some ridiculous guy who is even confused with tree traversal. "the recursion will blow up exponentially" I have to say this is the best piece of his answer. 

Also the 2nd comment from this guys seems useful, but how many times you have encountered that we are given parent pointer?

I beg this guy to take more CS class and do programming exercises before showing off his stupidity

Sigiloso · Answer

For either of these solutions, the recursion will blow up exponentially.  You'll need to either find a solution which only recursively calls itself once or an iterative algorithm.

Also, if the binary tree includes a pointer to the parent, then the fastest will be to start from T2 and search parents.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas