Lowest Common Ancestor

Lesson 14 of 16 in Coddy's AVL Tree - Data Structures Series #10 course.

The lowest common ancestor of two values is the deepest node that has both of them somewhere in its subtree. In a binary search tree, you can find it without ever comparing subtrees directly: starting from the root, if both values are smaller than the current node, the answer is somewhere in the left subtree; if both are larger, it's in the right subtree.

The moment the two values fall on different sides (or one of them equals the current node), you've found the split point: that node is the lowest common ancestor.

Challenge

Easy

Write a function lca(tree, p, q) that returns the value of the lowest common ancestor of p and q. You may assume both values exist in the tree.

Try it yourself

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int p1 = atoi(strtok(NULL, " \n"));
    int result = lca(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}