## Riverbed Interview Question for Software Engineer / Developers

Country: United States

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

I guess recursion should do.

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

something like ....

boolean isSubTree(t1.root, t2.root) {
if(t1.root == null || t2.root == null) {
return false;
}
else if(t1.root == t2.root) {
return isExactMatch(t1.root, t2.root);
}
else {
return ((isSubTree(t1.root, t2.left)) || (isSubTree(t1.root, t2.right)));
}

boolean isExactMatch(t1.root, t2.root) {
if(t1.root == t2.root) {
if(t1.root == null) {
return true;
}
else {
return isExactMatch(t1.left, t2.left) && isExactMatch(t1.left, t2.left);
}
}
else
return false;

if it were not a binary tree then we need to iterate over all the children instead of just right and left. Please point it out if there is some flaw.

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

A bit typo i guess..

return isExactMatch(t1.left, t2.left) && isExactMatch(t1.right, t2.right);

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

Write in-order trasversals of both trees, and then check is tree1's trasversal contains tree2 trasversal as subsequence?

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

@V.Krestyannikov: I do not think so.

The following two trees have, [15 16 17 18 19 20] and [15 16 17] as their in order traversals. However, I do not think the second tree can be considered a sub-tree of the first.

__17__
/      \
15      19
\    /  \
16  18  20

__16__
/      \
15      17

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

yes, you are right, I'll think about it.

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

@V.Krestyannikov: However, I think you are on right track. I am guessing, if we any compare "two" different traversals (in and pre, pre and post or in and post) and see that the smaller tree-traversal is a subsequence of the larger one, the smaller one should be a subtree.

Again, we are assuming a *binary* tree. The problem will be different if it is a general tree.

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

You can add some more info the the traversal, like in the actual list from inorder traversal add info containing the path it took for the traversal (15R16PP17R19L18PR20). This can also be modified for any other tree.

I any case i agree that comparing tree traversals will be better than comparing trees directly as we can not directly guess where (if) the sub tree will fit into the main tree.

Again* , we are (actually I am) assuming nodes implement some ToString() method. Trees with complex nodes will create issues as to store/compare traversals might not be viable.

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

Assuming Binary Search Tree: Doing full tree traversal will make you traverse every node of both the trees. It's inefficient. Basically find the root node (of the tree to search) in the other tree, and from there just do direct tree comparision (i.e. traverse one in certain order and ensure the other has exactly same order).

If it is generic tree: Again follow the above procedure but it takes more effort to search the root element (you have to do a plain dumb search) and also there is possibility of root element being at more than one place.

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

This will not work.

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

A little detail: we need to compare the data in the nodes, not the nodes themself.

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

#include <stdio.h>
#include <stdlib.h>

/* 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)
{
/* 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);
}

/* Helper function that allocates a new node with the given data
and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node =
(struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}

/* Driver program to test above function */
int main()
{
// TREE 1
/* Construct the following tree
26
/ \
10 3
/ \ \
4 6 3
\
30
*/
struct node *T = newNode(26);
T->right = newNode(3);
T->right->right = newNode(3);
T->left = newNode(10);
T->left->left = newNode(4);
T->left->left->right = newNode(30);
T->left->right = newNode(6);

// TREE 2
/* Construct the following tree
10
/ \
4 6
\
30
*/
struct node *S = newNode(10);
S->right = newNode(6);
S->left = newNode(4);
S->left->right = newNode(30);

if (isSubtree(T, S))
printf("Tree 2 is subtree of Tree 1");
else
printf("Tree 2 is not a subtree of Tree 1");

getchar();
return 0;
}

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.