Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
Start preorder traversal of T1 till either T2 is found or full tree has been traversed.
Case 1. T2 is found: Do preorder traversal of both trees together and keep comparing the nodes. If all nodes same till T2 is completely traversed, T2 is a subtree of T1.
Case 2: Check if T1 is a subtree of T2.
It's important that the trees are ordered the same way.
If both trees are equivalently order (lets say the comparison operator for comparing trees is called "compare"), then the code would look like this:
javascript
function Tree(children){
this.children = children || [];
this.children.sort(compare);
}
Tree.prototype = {
constructor : Tree,
equals : function(obj){
return compare(this,obj) == 0;
},
contains : function(obj){
if(this.equals(obj))
return true;
for(var c in this.children){
if(compare(this.children[c],obj) == 0)
return true;
if(this.children[c] instanceof Tree && this.children[c].contains(obj))
return true;
}
return false;
}
};
Here is an example of a "compare" function
javascript
function compare(a,b){
if(a instanceof Tree && b instanceof Tree){
// sort Trees with more children first
if(a.children.length != b.children.length){
return a.children.length - b.children.length;
}
for(var i = 0; i < a.children.length; ++i){
var comparison = compare(a.children[i],b.children[i]);
if(comparison != 0)
return comparison;
}
return 0;
}
// sort other objects before trees
if(a instanceof Tree){
// change trees with one child into objects for sorting purposes
if(a.children.length == 1)
a = a.children[0];
else
return 1;
}
if(b instanceof Tree){
// change trees with one child into objects for sorting purposes
if(b.children.length == 1)
b = b.children[0];
else
return -1;
}
// sort comparable objects in ascending order
if(a>b){
return 1;
}
if(a<b){
return -1;
}
return 0;
}
Here are some test cases:
javascript
var a = new Tree([7,5,2,new Tree([6, 4, 3])]);
var b = new Tree([3,6,4]);
var c = new Tree([4]);
var d = new Tree([2,7]);
console.log (b.contains(c)); //true
console.log (a.contains(c)); //true
console.log (a.contains(b)); //true
console.log (a.contains(d)); //false
Here is the same example using arrays as trees:
javascript
function contains(arr1,arr2){
if(compare(arr1,arr2) == 0)
return true;
for(var a in arr1){
if(contains(arr1[a],arr2))
return true;
}
return false;
}
function compare(a,b){
if(a.sort)
a.sort(compare);
if(b.sort)
b.sort(compare);
if(a.length == 1)
a = a[0];
if(b.length == 1)
b = b[0];
// sort other objects before arrays
if(a>b || (!a.length && b.length)){
return 1;
}
if(a<b || (!b.length && a.length)){
return -1;
}
return 0;
}
var a = [7,5,2,[6,4,3]];
var b = [3,6,4];
var c = [4];
var d = [2,7];
console.log (contains(b,c)); //true
console.log (contains(a,c)); //true
console.log (contains(a,b)); //true
console.log (contains(a,d)); //false
First see the levels of trees..the tree(T2) with more levels will obviously cover the other one(T1).
now for T1's each element,
recursively search elements in T2 and if all nodes match return true ...
if it is part of that tree.then match only root of small tree.because address of the small tree would be same as the address of a node of bigger tree.then no need to match further because if address is same then other address would be same.if every data structure is same.
if it says that we want to search value of small tree should be same subtree on bigger tree if it present there.then take a queue put bigger tree nodes on that and search every element from small tree from root of the small tree.
fdb fdvbfdbfdvb fdvbfgdvb gf
- vfdvfdbfdb March 24, 2012