Any two separate nodes in a binary tree have a common ancestor, which is the root of a binary tree. The lowest common ancestor(LCA) is thus defined as the node that is furthest from the root and that is the ancestor of the two nodes.
The following are binary trees and the lowest common ancestors of the some of their nodes.
The LCA of 13 and 15 is 14.
The LCA of 47 and 49 is 48.
The LCA of 4 and 45 is 40.
The LCA of 13 and 14 is 14.
The LCA of 15 and 47 is 40.
Challenge
Write the shortest program possible that accepts as input the root of a binary tree and references to any two nodes in the binary tree. The program returns a reference to the LCA node of the two inputted nodes.
Assumption
Assume there is a least common ancestor present for any two nodes in the binary tree.
Input
The root of a binary tree and references to any two nodes in the binary tree that the lowest common ancestor must be found for. The root of the binary tree may be in the form of a reference to the root object or even a list that is a valid representation of a binary tree.
Output
If using a pointer-based representation of a tree returns a reference to the node that is the LCA of the two inputted nodes.
If using a list representation returns the node_id for the lowest common ancestor of the two inputted nodes.
Definition of a Binary Tree
A tree is an object that contains a value and either three other trees or pointers to them.
The structure of the binary tree looks something like the following:
typedef struct T
{
struct T *l;
struct T *r;
struct T *p; //this is the parent field
int v;
}T;
If using a list representation for a binary tree and since certain node values in the binary tree may reappear, the list representation must have an additional node_id parameter that looks something like this:
[[node_id,node_value],left_tree, right_tree, parent_tree]