Amazon Interview Question Software Development Managers
Country: India
Interview Type: Phone Interview
It is not clear if the tree is a binary tree or not. Algo varies depending on the tree type.
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.
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.
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.
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.
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.
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..
/* 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);
}
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;
}
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;
}
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) );
}
the else part must like this i suppose.. Correct me if am wrong...
else
return(isSubTreeOrNot(tree1->left,tree2) || isSubTreeOrNot( tree1->right, tree2));
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.
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)
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.
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.
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!!!
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;
}
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
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)
// 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);
}
Check if inorder as well as preorder of A is contained in inorder or preorder of B.
- Learner August 26, 2012