Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Create an algorithm to decide if T2 is a subtree of T1.
function containTrees(tree1, tree2){
if (tree2 === null){
return true;
}
return subTree(tree1, tree2);
}
function subTree(tree1, tree2){
if (tree1 === null){
return false;
}
if (tree1.val === tree2.val){
return matchTree(tree1, tree2);
}
return subTree(tree1.left, tree2) || subTree(tree1.right, tree2);
}
function matchTree(tree1, tree2){
if ((tree1 === null) && (tree2 === null)) return true;
if (tree1 === null || tree2 === null) {
return false;
}
if (tree1.val !== tree2.val){
return false;
}
return (matchTree(tree1.left, tree2.left) && matchTree(tree1.right, tree2.right))
}
// var large = {val:10, left:null, right:null};
// var a = {val:1, left:null, right:null};
// var b = {val:2, left:null, right:null};
// var c = {val:3, left:null, right:null};
// var d = {val:4, left:null, right:null};
// large.left = a;
// a.left = b;
// a.right = c;
// b.left = d;
// var small = {val:1, left:null, right:null};
// var b = {val:2, left:null, right:null};
// var c = {val:3, left:null, right:null};
// var d = {val:4, left:null, right:null};
// small.left = b;
// small.right = c;
// b.left = d;
// console.log(containTrees(large, small));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.