Amazon Interview Question Software Development Managers


Country: India
Interview Type: Phone Interview


Comment hidden because of low score. Click to expand.
3
of 3 vote

Check if inorder as well as preorder of A is contained in inorder or preorder of B.

- Learner on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not clear if the tree is a binary tree or not. Algo varies depending on the tree type.

- victor on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry. It is a binary tree but not a BST

- hari@hbiz.in on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the logic behind checking preorder too?

- hari@hbiz.in on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Regarding Hari's question:

If trees are like this:
1
/ \
2 3
/ \ / \
4 5 6 7

1
/ \
5 6

Then inorder of A: 4251637 and inorder of B: 516. Even though inorder of B is contained in A, B is not a subtree of A. That is why you need to check both types of traversals before declaring one tree is a subtree of another.

- DC on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very good point. But preorder testing is required only if you are given the tree in form of list or array. If the tree itself is given, then any one traversal is sufficient with node by node comparison.

- hari@hbiz.in on August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ hari@hbiz.in
But in spite of this algorithm by Learner is O(n + k) while your algorithm takes O(nk) in the worst case.

- Aleksey.M on January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Travel through tree A, and search for node B if not found, travel through Tree B and search for node A. If you found in either case, compare the elements.

- hari@hbiz.in on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typedef struct TNode
{
	int value;
	TNode *left;
	TNode *right;
} TNode;

bool ifExist(const TNode* treeA, const TNode* treeB);

bool isSubtree(const TNode* treeA, const TNode* treeB)
{
     if (treeB == NULL) 
     {
         // if treeB is null no point in searching.
         return true;
     }
     bool a_has_b = ifExist(treeA,treeB);
     bool b_has_a = false;	
     // Check only if treeB is not found in treeA.
     if (!a_has_b)      
        b_has_a= ifExist(treeB,treeA);
      
     return a_has_b || b_has_a;
}


bool ifExist(const TNode* treeA, const TNode* treeB)
{
    if ( treeA == NULL && treeB != NULL)  
    {
	   // We reached the end of path. No subtree found.
	   return false;
    }
    if ( treeA == treeB)
    {
	   return CompareTheSubtree(treeA,treeB);	   
    }
    return ifExist(treeA->left,treeB)|| ifExist(treeA->right,treeB);
}

Note : I have not written CompareTheSubtree() method as it is trivial.

- hari@hbiz.in on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, Why do you need to compare the elements. Once you found treeA == treeB,
address is same so no need to check further.

- rishi t on September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

check for a tree by traversing it, whether at some point it is equal to the root of other tree. if it is, it is the subtree else not.

- Ashish on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if tree A is like 1
/ \
2 3
and tree B is like 2
/ \
4 5
in this root of B is present in root of A but in Tree A I don't want to include further tree..So according to your answer if node of B will present in A then we have to traverse till end of tree B and check all are present in A or not..

- Anonymous on September 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static boolean doesContainsSubTree(Node a, Node b)
{
if(a==null && b== null)
return true;
else if((a!= null && b==null)|| (a==null && b!= null))
return false;
else
{
if(a.data == b.data)
return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
else
return doesContainsSubTree(a.left, b) || doesContainsSubTree(a.right, b);
}
}
public static boolean isSameTree(Node rootA, Node rootB) {
if(rootA == null && rootB == null)
return true;
else if(rootA != null && rootB != null)
return rootA.data == rootB.data && isSameTree(rootA.left, rootB.left) && isSameTree(rootA.right, rootB.right);
else
return false;
}

- Shishir on August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

be real...

- Anonymous on August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

My Idea is get the length of both the trees and whoever is larger could surely be the Super tree and another will be subtree if they one of them is part of the other and to find whether the smaller tree is part of larger tree we will recursively check if the left and right subtrees are exactly same if the respective is not null in the smaller tree

function isSubTree(Node root1, Node root2)
   {
              int length1 = lengthOfTree(root1);
              int length2 = lengthOfTree(root2);
              if(length 2 > length1)
              {
                     root2 = findNodeInTree(root2, root1); // find root1 in tree2(root2)
                     return isSubTreeOf(root2, root1)
               }
              
              else{
                root1 = findNodeInTree(root1, root2); // find root2 in tree1(root1)
                return isSubTreeOf(root1, root2)          
             }

   }   
    function isSubTreeOf(Node rootOfSuperTree, Node rootOfSubTree)
    {
       boolean isleftChildSubTree = true;
       boolean isRightChildSubTree = true;
       if(rootOfSubTree.value == rootOfSuperTree.value)
      { 
           if(rootOfSubTree.leftChild != null)
           {
                      isleftChildSubTree= isSubTreeOf(rootOfSuperTree.leftChild , rootOfSubTree.leftChild);
           }
            else{
                       isRightChildSubTree= isSubTreeOf(rootOfSuperTree.rightChild , rootOfSubTree.rightChild)
             
            }
       return isRightChildSubTree && isleftChildSubTree;

       }
        else
          return false;

    }

- anshulzunke on September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are they labelled?

- Anonymous on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
- Aalok on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

calling same function two times gives the desired result by interchanging the trees.

int isSubTreeOrNot(struct BTree *tree1, struct BTree *tree2)
{
	if( (!tree1  && !tree2 ) || (tree1 && !tree2) )
		return 1;
	else if((!tree1 && tree2))
		return 0;
	 else if(tree1->data == tree2->data)
		return( isSubTreeOrNot(tree1->left,tree2->left) && isSubTreeOrNot(tree1->right, tree2->right) );
	 else 
		return( isSubTreeOrNot(tree1->left,tree2) && isSubTreeOrNot(tree1->right, tree2) );
}

- Aalok on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the else part must like this i suppose.. Correct me if am wrong...

else
return(isSubTreeOrNot(tree1->left,tree2) ||     isSubTreeOrNot( tree1->right, tree2));

- vinodhian on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@vinodhian, Thanx for pointing my mistake.
It should be ||(or) instead of &&(and).

- Aalok on August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

have you tried executing this? I dont think this works.

- BJ on September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code won't work as you have combined two functionality into single function.
[1] searching T2's root into T1 tree.
[2] After finding T2's root in T1, checking if entire T2 exists into T1.

This is because of following example.

T1:

4
/ \
2 6
/ \ / \
1 3 5 8
\
9

T2:
6
/ \
5 9

In this case when you call isSubTreeOrNot(T1,T2), it will first try to search 6 in T1. Once it finds it, it will return true for (6,6) and (5,5) calls which is correct so far. But when you call isSubTreeOrNot(8,9) it will go in if condition try to search 9 in the sub trees of node 8 of T1. Eventually it will return true and whole function call will return true where as it was supposed to return false.

I know It's kinda confusing. I tried my best to explain my point. We need to pass a flag which indicates that we are not supposed to try to search T2's node in T1.

- G10 on April 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is corrected code. I've also optimized the search. In your case even though T2 is part of T1.right, it will go and search for T2.root in entire T1.left because in your else condition you search for T2 in T1.left before in T1.right.



Corrected code:

def isSubTreeOrNot(T1,T2,search):
    if T2==None:
	return True
    elif T1==None:
	return False

    if T1.data == T2.data:
	return isSubTreeOrNot(T1.left,T2.left,search) and isSubTreeOrNot(T1.right, T2.right,search)

    if search:
        if T1.data>T2.data:
            return isSubTreeOrNot(T1.left,T2,search)
        elif T1.data<T2.data:
            return isSubTreeOrNot(T1.right,T2,search)
        else:
            return isSubTreeOrNot(T1,T2,False)
    else:
        return False

isSubTreeOrNot(T1,T2,True)

- G10 on April 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is binary tree a binary search tee?

- victor on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no. binary tree has numbers arbitrarily placed unlike BST.

the in-order of a binary SEARCH tree gives a sorted output but the in-order of binary tree does not.

- krishnakanth on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks!
Since in the question, it is not clear whether this is meant for binary tree or not.
Thanks for clarifying.

- Victor on August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this a binary tree?

- victor on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* A binary tree node has data, left child and right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
 
/* A utility function to check whether trees with roots as root1 and  root2 are identical or not */
bool areIdentical(struct node * root1, struct node *root2)
{

    if(root1 == NULL && root2 == NULL)
        return true;
 
    if(root1 == NULL || root2 == NULL)
        return false;
 
    /* Check if the data of both roots is same and data of left and right
       subtrees are also same */
    return (root1->data == root2->data   &&
            areIdentical(root1->left, root2->left) &&
            areIdentical(root1->right, root2->right) );
}
 
/* This function returns true if S is a subtree of T, otherwise false */
bool isSubtree(struct node *T, struct node *S)
{   
    if (S == NULL)
        return true;
 
    if (T == NULL)
        return false;
 
    /* Check the tree with root as current node */
    if (areIdentical(T, S))
        return true;
 
    /* If the tree with root as current node doesn't match then
       try left and right subtrees one by one */
    return isSubtree(T->left, S) ||
           isSubtree(T->right, S);
}

- Jessica on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you're provided the root R of the subtree, then R should have a parent reference to the supertree. If you can find this parent reference, then you're done.

- Jack on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this should work.

Suppose we need to find whether B is subtree of A or not. Then find whether root of B is in A. If no then its not a subtree. if you find it, then do an inorder traversal of the subtree and compare that with the inorder of B. if both are equal then B is subtree of A.

- Vijay on August 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If both the trees have same Lowest Common Ancestor which is root of one of 'em itself.

- Second Attempt on August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sufficient in this case. Amazon expects us to check for subtrees.

- hari@hbiz.in on August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you point out cases which remain uncovered with LCA?

- Anonymous on August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about checking if value of root of Tree A is in Tree B and then checking their addresses? and vice-versa?

- Chinmay on August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Baby approach :P ......... count the number of nodes in both trees say A and B ....the tree with greater number of nodes will by default ...by theory will be the parent tree and the other with less nodes will be sub tree(probably) . Now to check weather the sub tree really belongs to the parent tree search for root node of sub tree in parent tree and when found start traversing both the trees simultaneously and if the traversing ends up with sub tree it means you just traverse the sub tree in the parent tree.. BINGO!!! :)....please correct me if I m wrong!!!

- skywalker on September 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean hasSubTree(BTNode T1, BTNode T2){
		return isSubTree(T1,T2) || isSubTree(T2,T1);
	}

public boolean isSubTree(BTNode superTree, BTNode subTree){
		if(superTree == subTree) return true;
		else if(superTree.left != null || superTree.right !=null) return (isSubTree(superTree.left,subTree) || isSubTree(superTree.right,subTree));
		else return false;
	}

- neet on October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS would find whether a tree is subtree or not..

- Bala on November 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

step 1: calculate the depth of both trees , d1 (depth of first tree)& d2(depth of second tree)
step 2: if d1 > d2, then second tree could be subtree of first tree
if d2 > d1, then first tree could be subtree of second tree
step 3: Do BFS traversal and search for subtree root node
step 4: if root node of subtree is found on BFS traversal of main tree then its fine

- Amit Singh on December 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

agreed

- Anonymous on December 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've tried to decompose all the conditions in three separate functions because not all the conditions are applicable to all the nodes. This fact becomes more significant when # of nodes in given trees is in terms of thousands.

def subTree(T1, T2):
    if T1==None or T2==None:
        return True
    return isSubTree(T1,T2) or isSubTree(T2,T1);

def isSubTree(T1,T2): #Finds T2.root in T1
    if T1 == None: # Reached Leaf of T1 but could not find T2.root yet
        return False

    if T1.data < T2.data: # Find T2 on left subtree of T1
        return isSubTree(T1.left,T2)
    elif T1.data > T2.data: # Find T2 on right subtree of T1
        return isSubTree(T1.right,T2)
    else: # compare both trees now as we found T2.root in tree T1
        return isSubTreeHelper(T1,T2)

def isSubTreeHelper(T1,T2):# Checks if T2 is subtree of T1
    if T2==None: # T2's branch ends then return true
        return True
    elif T1==None:# T1 ends before T2 then return False
        return False
    else: 
        return T1.data==T2.data and isSubTreeHelper(T1,T2) and isSubTreeHelper(T1,T2)

- G10 on April 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Java solution to this problem. Assumes the tree is not necessarily a binary tree. It can 
// have any number of children at any level. Also assume that the tree may or may not 
// have duplicates. Final assumption is that a leaf node initializes it's children list as an array of length 0.

class Node {
  public Node [] children;
  public Object value;
}

public static boolean isTreeEqual(Node treeA, Node treeB)
{
  if( treeA.value.equals(treeB.value) && treeA.children.length == treeB.children.length ) {
    if( treeA.children.length == 0 ) {
      return true;
    }
    for( int i = 0; i < treeA.children.length ; i++ ) {
      return isTreeEqual( treeA.children[i], treeB.children[i] );
    }
  }
  return false;
}

// Checks if "subTree" is a sub-tree of "tree"
public static boolean isSubTree (Node tree, Node subTree)
{
  if( tree.value.equals(subTree.value)) {
    if( isTreeEqual(tree, subTree) ) {
      return true;
    }
  } else {
    for( int i = 0; i < tree.children.length; i++ ) {
      Node newTree = tree.children[i];
      if( isSubTree(newTree, subTree) ) {
        return true;
      }
    }
  }
  return false;
}

public static boolean isSubTreeEitherWay( Node treeA, Node treeB )
{
  if( isSubTree( treeA, treeB) )
    return true;
  return isSubTree(treeB, treeA);
}

- Anonymous on August 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Do inorder traversal of the trees, if the inorder notation of one tree is contained in another 's inorder notation then it is a subtree else not

- Anonymous on August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

NO.

- Anonymous on August 26, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More