CareerCup4.7.cpp

CareerCup4.7.cpp

/*
 Chapter 4
 
 4.7  Design an algorithm and write code to find the first common ancestor
 of two nodes in a binary tree. Avoid storing additional nodes in a
 data structure. NOTE: This is not necessarily a binary search tree.
 */
// Assumption: when p is one ancestor of q's, we say p is the first common
//             ancestor of p, q

#include <iostream>

using namespace std;

typedef struct tNode {
    int value;
    struct tNode* left;
    struct tNode* right;
}tNode;

tNode* newNode(int v)
{
    tNode* node = new tNode;
    node->value = v;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Tricky part for me, recursion to traverse
bool inSubtree(tNode* root, tNode* target)
{
    if (root == NULL)
        return false;
    if (root == target)
        return true;
    return inSubtree(root->left, target) || inSubtree(root->right, target);
}

// First common ancestor
tNode* firstCommon(tNode* root, tNode* p, tNode* q)
{
    // Error Check: p, q not in this binary tree
    if (!inSubtree(root, p) || !inSubtree(root, q))
        return NULL;
    // One of them is root, treat as their first common ancestor
    if (root == p || root == q)
        return root;
    // Case 1: p, q locate in different side of root
    //         first common ancestor must be root
    if (inSubtree(root->left, p) != inSubtree(root->left, q))  {
        return root;
    }
    // Case 2: p, q locates in same side of root
    // sub-case-1: p,q both in left of root
    // focus on left subtree and recurse on it
    if (inSubtree(root->left, p)) {
        return firstCommon(root->left, p, q);
        
    }
    // sub-case-2: p,q both in right of root
    // focus on right subtree and recurse on it
    if (inSubtree(root->right, p)) {
        return firstCommon(root->right, p, q);
    }
    return NULL;
}

// Main Function to test
int main()
{
    /*      5
           /   \
         3      10
        / \    /
       1   4  7      */
    tNode* root = newNode(5);
    tNode* a = newNode(1);
    tNode* b = newNode(3);
    tNode* c = newNode(4);
    tNode* d = newNode(10);
    tNode* e = newNode(7);
    root->left = b; root->right = d;
    b->left = a; b->right = c;
    d->left = e;
    // Find the first common ancestor
    tNode* firstcommon = firstCommon(root, a, e);
    if (firstcommon)
        cout << "Their first common ancestor is:  " << firstcommon->value << endl;
    else
        cout << "Not found." << endl;
    return 0;
}