First Common Ancestor

4.8 First Common Ancestor: 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.

• This problem is similar to finding the intersection of two linked lists.

• The first common ancestor of two nodes is also the first intersections of two nodes in a binary tree.

• I am going to assume that each node has accessibility to its parent.

• As a reminder, depth measures the number of edges a particular node has to its root, while the height of a tree measure the number of edges a particular node has to its deepest leaf. We use depth to measure distance because we are going to be traversing UP the tree, rather than down.

struct Node {
       int val;
    Node *left;
    Node *right;
    Node *parent;
    Node(int x, Node *p) : 
        val(x), left(NULL), right(NULL), parent(p) {}
};

Node* firstCommonAncestor(Node *one, Node* two) {
    if (!one || !two) return nullptr;

    int distance = depth(one) - depth(two);

    // if (-), then two is larger, so increment it first, and vise-versa
    if (distance < 0) {
        for (int i = 0; i < abs(distance); i++) {
            two = two->parent;
        }
        // now increment at the same time
        while (one != two) {
            one = one->parent;
            two = two->parent;
        }
    }
    else {
        for (int i = 0; i < abs(distance); i++) {
            one = one->parent;
        }
        // now increment at the same time
        while (one != two) {
            one = one->parent;
            two = two->parent;
        }
    }

    return one; // or two

}

int depth(Node *node) {
    int depth = 0;
    while (node->parent) {
        depth++;
        node = node->parent;
    }
    return depth;
}

• Now I am going to assume that the the parent of each node is not in the Object of Node.

struct Node {
    int val;
    Node *left;
    Node *right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};

• Now I am going to assume that the the parent of each node is not in the Object of Node.

• The idea goes as follows:

  • First we check the base condition: we will assume that a node cannot be a descendent of itself. So that if both nodes are shared across the same linage, then will return null. This is what the first condition checks for. Either the root is null to begin with or q contains p or p contains q.

  • Now we can step into the recursive condition: but we first have to understand the following:

    • One, the root is always the highest common ancestor of all nodes, since all nodes can trace their linage all the way up to the root.

    • Two, the first instance starting from the root that q and p a are on different sides of the tree, we know the root is the lowest common ancestor. This is because all the previous ancestoral nodes before are were some level of the highest common ancestor.

  • So the question now lyes: what part of the tree do we descend down? Well, if p_contained_in_left != q_contained_in_right, it could either be one of the two: !p_contained_in_left == q_contained_in_right or !q_contained_in_right == p_contained_in_left. The first one says that both p and q are contained in the right child of the subtree. The second one says both p and q are contained in the left child of the subtree. So we always continue to descend down the tree that contains both p and q.

Node* lowestCommonAncestor(Node* root, Node* p, Node* q)
{
    if (!root || contains(p, q) || contains(q, p))
        return nullptr;

    return lowestCommonAncestor_helper(root, p, q);
}

Node* lowestCommonAncestor_helper(Node *root, Node *p, Node *q)
{
    bool p_contained_in_left = contains(root->left, p);
    bool q_contained_in_right = contains(root->right, q);

    if (p_contained_in_left == p_contained_in_left)
        return root;

    if (!p_contained_in_left == q_contained_in_right)
        lowestCommonAncestor_helper(root->right, p, q);
    else if (p_contained_in_left == !q_contained_in_right) 
        lowestCommonAncestor_helper(root->left, p, q);
}

bool contains(Node *root, Node *_this)
{
    if (!root) return false;
    else if (root == _this) return true;
    return contains(root->left, _this) || contains(root->right, _this);
}