Saturday, September 3, 2011

Find whether given tree is a subtree or not


Given two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.

 Pseudo code :
check( node t1 , node t2 ) 
{
   if ( t1->data == t2->data)
  {
     return check( t1->left , t2->left ) && check(t1->right, t2->right) ; 
  }
  else
  {
     return check(t1->left , t2) || check(t1->right , t2); 
  }
}

Time complexity :O(n) because each node in T1 needs to be visited once.

1 comment: