Jul 302012
 

Write function to check whether two trees are similar or not. The signature of the function should be as shown below:

    /** 
     * Function to check whether two trees are similar or not.
     * @param r1, r2: Pointer to root nodes of two trees.
     * Returns true(1) if the two are similar, else false(0)
     */
    bool isSimilar(Node* r1, Node* r2);

Two trees are similar if they have same structure else they are not similar. Below pictures show Similar and non-similar (different) trees:

                


Algorithm:

1. If both Trees are NULL or have only one node
      return TRUE
2. If either r1 is NULL or r2 is NULL (but not both)
      return FALSE 
2. Call this function recursively for Left sub-tree pointers (r1->lptr, r2->lptr)
3. Call this function recursively for Right Sub-tree pointers (r1->rptr, r2->rptr)

 Code:

    /** Function to check if two trees are similar or not
     */
    bool similarTrees(Node* r1, Node* r2)
    {
        // If both are NULL
        if (r1 == NULL && r2 == NULL) 
            return true;

        // If one of them is NULL
        if (r1 == NULL || r2 == NULL) 
            return false;

        // If both have only root node
        // (and not Left/right sub-tree)
        if(r1->lptr == NULL && r1->rptr == NULL && r2->lptr == NULL && r2->rptr == NULL)
            return true;

        // Calling recursively
        return ( similarTrees(r1->lptr, r2->lptr) &&  similarTrees(r1->rptr, r2->rptr) );
    }

 

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)