## Oracle Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

This is something that came to my mind. Correct me if I am wrong.

You can do the preorder traversal of the first tree. Store the result in a string. Do preorder traversal of second tree. Store result in second string. Find if second string is substring of first.

Next. Do the same for inorder traversal. If both the result come out to be true then T2 is subtree of T1.

Complexity will be : O(m+n).

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

Simply search for the root node of the smaller tree in the larger one. Once that is found, do a simultaneous traversals as the follows :

eq(t1, t2) = t1.data=t2.data && eq(t1.left, t2.left) && eq(t1.right, t2.right)

By doing this you can break once equality fails.
Complexity in the worst case is still O(m+n). However, the average case is much better.

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

Are you guys sure the complexity is the worse case is still O (m +n ) Think about the case almost every node in T1 match T2.root, so you have to look for T2 in T1 many many times. Imagine that It only differ on one Node ( on the T1 subtree )
then you have to look the whole T1 ( O (n ) ) times T2 ( O (m - x ) where x is the number of nodes that did not match. then It ends up like O (n*(m-x)) ~ O(n*m) which is much more thatn O (n +m )
What do you think? If you don't agree elaborate more no the complexity please.

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

Good one coder...

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

We don't want millions on a recursive traversal right ?

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

Why do you need another inorder traversal?

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

Complexity O (m*n) worse case scenario

``````public static boolean isSubTree(TNode t1, TNode t2)
{
if( t1 == null && t2 == null) return true;
if( t1 == null) return false;

if(t2 == null  || (t1.value == t2.value && containsTree(t1,t2))){

return true;

}else{
if(t1.value > t2.value){
return isSubTree(t1.left,t2);
}else{
return isSubTree(t1.right,t2);
}
}
}
public static boolean containsTree(TNode t1, TNode t2)
{
if( t2 == null ) return true;

if( t1.value == t2.value ){
return containsTree(t1.right,t2.right) && containsTree(t1.left,t2.left);
}else{
return false;
}

}``````

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

First we find t2 in t1 , it costs O(n), then we compare the two trees costs O(m), the overall should be O(n+m), correct me if I am wrong

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

Sorry, I make a mistake, the worse case should be O(m*n)

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

You are doing recursively. So for millions of node very soon you will get stack overflow error.

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

Here is an optimization. Since T1 is too big, we don't want to do it recursively right? So what about a BFS like this:

``````public static boolean isSubtree2(TNode t1, TNode t2){
while(!queue.isEmpty())
{
TNode current = queue.poll();
if(equalTree(current, t2)){
return true;
}else{
if(t2.value < t1.value){
}else{
}
}
}
return false;
}``````

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

equalTree could or not be recursivly since we are taking about hundred of nodes, which is not that big. But we can for sure make this none recursive and make it better.

``````public static boolean equalTree(TNode t1, TNode t2){
if(t2== null) return true;
if(t1== null) return false;
if(t1.value == t2.value){
return equalTree(t1.left, t2.left) && equalTree(t1.right,t2.right);
}else{
return false;
}
}``````

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

If it was not a Binary Search Tree then we can just change the folowing lines

``````if(t1.value > t2.value){
return isSubTree(t1.left,t2);
}else{
return isSubTree(t1.right,t2);
}``````

TO:

``return isSubTree(t1.left,t2) || isSubTree(t1.right,t2);``

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

I assume it's not a binary search tree. BSTs usually don't permit multiple nodes with the same value, so the algorithm would be trivial for a BST: search for the root of the small tree in the large tree, call the node found X, and check whether the subtree at X is identical to the small tree.

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

This is too much of a question:
1.With two millions of nodes coming into memory can I have another two million nodes memory available.
2. The lesser the memory the more the complicated the code is going to get.
3. Say there is not enough memory to bring 1/4 of any tree, the solution would be different then
4. If the entire tree cannot come into memory, is the tree in a Database, a file, ...In such a case it is an art to parse the tree itself [one needs to use memory mapped files]
5. If my Memory is small and hard disc is small and/or the Tree data is itself distributed in some 100 computers, then the solution lies in a distributed architecture.
6. If we go on like this, one can see that the actual solution to compare trees looks abysmal.
7. I wonder why they ask such difficult question.
8. In the Mathematics world this question would be rejected for not being precise.

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

``````/* 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)
{
/* base cases */
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)
{
/* base cases */
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.
0
of 0 vote

You could always come up with a sort of hash function that was dependent on the current node, and the hash values of the left/right children.

In O(n) time you are able to calculate the hash value of the root node of the smaller tree.
And then in O(m) time you are able to calculate all node hash values in the larger tree. As you're cycling through the nodes of the larger tree, you're comparing the hash keys.

This solution would be O(m+n) time. With the only complications coming from possible key collisions.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is not O(m), can you please check again, it will be O(mn)

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

Here is solution with O(m) complexity. m - Number of nodes in the larger tree.

``````public static boolean isSubTree(TreeNode p, TreeNode s) {
if (p == s & p == null) {
return true;
} else if (p == null || s == null) {
return false;
}

if (p.getData() == s.getData()) {
return isSubTree(p.getLeft(), s.getLeft())
&& isSubTree(p.getRight(), s.getRight());
} else {
return isSubTree(p.getLeft(), s) || isSubTree(p.getRight(), s);
}
}``````

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.