You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
Approach 1:
T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.
Approach 2:
Find all the occurances of T2's root node in T1 and then check recursively if the binary tree matches or not.
Approach 1:
T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.
Approach 2:
Find all the occurances of T2's root node in T1 and then check recursively if the binary tree matches or not.
this can be made faster...
ReplyDeletei guess the compiler should be smart enough to do this by its own..
but just in case.. instead of
return (matchBinaryTree(A.left, B.left) && matchBinaryTree(A.right, B.right));
we can first check matchBinaryTree(A.left, B.left) and if its true then only we go for the second call, else just return false.