CareerCup

Just to be clear: are we talking about a binary tree, a BST, or any tree in general?

in any case,
Method 1 : memory inefficient, time + code efficient.
1. take the inorder traversal of both the trees.
2. find the longest subsequence in the two arrays.
3. if one of the array is entirely the longest subsequence, you got it, else not.

Method 2: memory efficient, time inefficient.
1. search for the root of one tree in the other.
2. if found try to match the structure, from there, using inorder as well as preorder traversal.

I think second method is more efficient.
@luvtheedragon: could you explain how method 2 is less time efficient than method 1.

As per my understanding
suppose if Bigger tree contains N node and smaller tree contains M node.
as per first method we will traverse both the trees that would cost us

O(M+N)

then we will also traverse both the array for finding longest common match...
which will also cost O(M+N)


while in method 2:

we search the root of smaller tree in bigger tree : O( Log N)
once found we traverse both the tree to compare each node. a pre order traversal O(M)

so method would cost ( M+ Log N )

please correct me folks if i am wrong

@Crime_Master_GoGO
How can you search a node in a binary tree (not BST) in O(log N)

may sound absurd but does a subtree
1. Nodes are same ? (ReferenceEqual)
2. Or just check if Data part of the node arranged in same order? (DataEqual)

If its #1 it can be found in O(n). Just traverse the bigger tree and return if you find the root of smaller tree found (referenceEqual).

For #2 Method 2 from luvtheedragon's solution

1. Write an Equals function that iteratively compares if 2 trees are equal
2. For the parent tree, for each node, call Equals till no nodes are left or Equals is true.

Some Java code I just wrote for a BST:

public boolean hasSubTree(BinarySearchTree sub) {
// Try to find head of subtree
TreeNode subHead = this.findNode(sub.root);
if ( subHead == null ) {
System.out.println("Tree head: " + sub.root.data + " NOT found!");
return false;
}

// Ok we found the head let's step on node and see if it matches
return this.navigateAndCompare(subHead, sub.root);
}

private boolean navigateAndCompare(TreeNode n1, TreeNode n2) {
if ( n1 == null && n2 == null ) {
return true;
}
if ( n2 != null && n1 == null ) {
return false;
}
if ( n1 != null && n2 == null ) {
return false;
}
if ( n1.data.equals(n2.data) ) {
boolean left = this.navigateAndCompare(n1.left, n2.left);
boolean right = this.navigateAndCompare(n1.right, n2.right);
if ( left && right ) {
return true;
}
return false;
} else {
System.out.println(n1.data + " does NOT match " + n2.data);
return false;
}
}

private void l(Object o) {
System.out.println(o);
}

public TreeNode findNode(TreeNode node) {
return this.findNode(this.root, node);
}

public TreeNode findNode(TreeNode n, TreeNode node) {
if ( node == null ) {
return null;
}
while ( n != null ) {
if ( n.data.equals(node.data) ) {
return n;
}
if ( node.data.compareTo(n.data) < 0 ) {
return this.findNode(n.left, node);
} else if ( node.data.compareTo(n.data) > 0 ) {
return this.findNode(n.right, node);
}
throw new RuntimeException("It should never get here!");
}
return null;
}

// returns true if n2 is subset of n1

bool isSubset( Node* n1, Node* n2 )
{
    if( n1==0 && n2!=0 )
    	return false;

    if( (n1!=0 && n2==0) || (n1==0 && n2==0) )
    	return true;

    return ( isSubset(n1->right, n2->right) && isSubset(n1->left, n2->left) );
}

can we map the tree with larger depth to hash table
and then search the sencond one in that table?????

plz comment!!!!

can we map the tree with larger depth to hash table
and then search the sencond one in that table?????

plz comment!!!!

Compare the tree structures if root has been found. Let the tree in which we are looking for a subtree be called super tree and tree to look for be subtree.

// superNode: node in the super tree
// subNode: node in the sub tree
// originalSubNode: original node in subtree i.e. root of subtree we are checking
bool IsSubTree(TreeNode superNode, TreeNode subNode, TreeNode originalSubNode)
{
   if ((superNode == null)&&(subNode == null))
   {
       return true;
   }

   if ((superNode == null)||(subNode == null))       
   {
       return false;
   }

   if (superNode.Key == subNode.Key)
   {
      bool leftResult = IsSubTree(superNode.Left, subNode.Left, originalSubNode);
      bool rightResult = IsSubTree(superNode.Right, subNode.Right, originalSubNode);
      
      if (leftResult && rightResult)
      {
          return true;
      }
   }

   // Either root is not equal or subtree was not found, try in subtrees
   return IsSubTree(superNode.Left, originalSubNode, originalSubNode) ||
          IsSubTree(superNode.Right, originalSubNode, originalSubNode);
}

bool IsSubTree(TreeNode superRoot, TreeNode subRoot)
{
    return IsSubTree(superRoot, subRoot, subRoot);
}

The key is to have originalSubNode so if a search fails, one can start fresh search in the subtree of super tree!