3
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]
1Could you provide exact input and output examples? Also, what if my programming language doesn't support references, pointers and structures? – Krzysztof Szewczyk – 2019-08-15T17:18:18.323
1If your language does not support references, you can use a list-like representation of a tree: [root_value, left_node, right_node, parent_node]. – T. Salim – 2019-08-15T17:22:45.860
1How is the list representation supposed to work? Having both the parent tree and child trees as sublists leads to an obvious infinite regress (and if they're not sublists, we're back to needing a reference-based representation). – Grimmy – 2019-08-19T15:59:33.753