Amazon Interview Question SDE1s
-11of 11 votesGiven a tree, verify if it contains a subtree.
Country: India
Interview Type: In-Person
Why to further check for left and right by recursive calling. Just check for the root. If root has non empty left or right child then it contains a subtree else not.
@vgeek: how ?
@new coder: can you please explain further. Also, what is the time complexity of your algo ?
@yolo read this : This i am pasting from wikipedia to clarify your doubt search for the same by typing trees in the wikipedia i cannot paste the link here:
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T.[c][1] Nodes thus correspond to subtrees (each node corresponds to the subtree of itself and all its descendants) – the subtree corresponding to the root node is the entire tree, and each node is the root node of the subtree it determines; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).
static int c=0;
subtree( struct node *root)
{
struct node * temp=root;
if(temp->left!=NULL || temp->right !=NULL)
{
count++;
}
else
return;
subtree(temp->left);
subtree(temp->right);
}
if(count >1)
printf("subtree present");
Yes when do we say that a tree contains a subTree.I want to say there may be some preconditions.
How do you search for a substring in a string ? It should be present somewhere in between the string.
Similarly, the subtree should be present somewhere in the main tree.
children of root should also have children, if child node does not have child then its just a node not a tree
First of all, the question is incomplete, unclear..
To find if a tree has sub-tree , we just need to check and left or right child of root not being NULL.
The question should no be so simple..right ..!!!!
The question should be: given a subtree, find out if a tree contains this sub tree or not..
This is the tree version of question : given a substring, find out if it is present in a string or not..!!
This can be solved in two ways:
First solution:
1. Do an in-order traversal of tree1 and store the result in auxillary array (vector in C++ so that memory can grow dynamically)
2. Repeat step 1 for tree2
3. See if tree2 aux array is in tree1 aux array (similar to strstr)
Second solution:
1. Find minimum element in tree2 (leftmost child) and take this nodes value
2. Find this value in tree1
3. Keep finding inorder successor of this node in tree1 and tree2
4. If they match continue, it not return false
5. If tree2 is done with return true, it tree1 is done before tree 2 return false
First solution works even if duplicate elements are allowed in the tree. Second may not and will require more complicated solution.
public boolean containsSubtree(TreeNode root, TreeNode subTree) {
if(subTree == null) return true;
if(root == null) return false;
if(root.val == subTree.val) {
return containsSubtree(root.left, subTree.left) && containsSubtree(root.right, subTree.right);
}
else if(root.val > subTree.val) return containsSubtree(root.left, subTree);
else return containsSubtree(root.right, subTree);
}
can be done recursively by incrementing static variable count if node contains left or right child and then call function for left and right child
- new coder July 11, 2013if count >1 subtree is present