Riverbed Interview Question Software Engineer / Developers
0of 0 votesCheck if tree 1 is sub tree of another tree 2
Country: United States
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.
Write in-order trasversals of both trees, and then check is tree1's trasversal contains tree2 trasversal as subsequence?
@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
@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.
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.
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.
#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;
}
I guess recursion should do.
- Anonymous January 15, 2012