## Amazon Interview Question for 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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Sorry. It is a binary tree but not a BST

Comment hidden because of low score. Click to expand.
0

What is the logic behind checking preorder too?

Comment hidden because of low score. Click to expand.
2

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@ 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.

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.

Comment hidden because of low score. Click to expand.
0

``````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;
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.

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
1
of 1 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);
}``````

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;
}

Comment hidden because of low score. Click to expand.
0

be real...

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;

}``````

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

Are they labelled?

Comment hidden because of low score. Click to expand.
0
of 0 vote
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) );
}``````

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

This code won't work as you have combined two functionality into single function.
 searching T2's root into T1 tree.
 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.

Comment hidden because of low score. Click to expand.
0

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)``````

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

Is binary tree a binary search tee?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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

Is this a binary tree?

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.

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.

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Can you point out cases which remain uncovered with LCA?

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?

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!!!

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;
}``````

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

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

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

Comment hidden because of low score. Click to expand.
0

agreed

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)``````

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);
}``````

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

Traverse each tree in the same manner while serializing the node values to a string, one per tree. Then check if the longer string contains the shorter one.

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

Comment hidden because of low score. Click to expand.
0

NO.

Name:

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

### Books

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

### 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.