find the closest common ancestor

 

void common(TreeNode<T> * t1, TreeNode<T> * t2)
    {
        if(t1 == NULL || t2 == NULL)
        {
            cout << "They have no common predecessor because of dummy nodes!" << endl;
        }
        else if(t1 == t2)
        {
            cout << "They are equal so the common predecessor is themselves!" << endl;
        }
        else
        {
            common_dfs(root, t1, t2);
        }
    }

    int common_dfs(TreeNode<T> * cur, TreeNode<T> * t1, TreeNode<T> * t2)
    {
        if(cur == NULL) return 0;
        int re = 0;
        if(cur == t1) re += 1;
        if(cur == t2) re += 2;
        int lv = common_dfs(cur->left, t1, t2);
        int rv = common_dfs(cur->right, t1, t2);
        re += lv + rv;
        if(re == 3 && lv != 3 && rv != 3)
        {
            cout << "The common predecessor is: " << cur->element << endl;
        }
        else
        {
            return re;
        }
    }

Advertisements
This entry was posted in algorithm and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s