Shortest Program To Find Lowest Common Ancestor of Two Nodes in a Binary Tree

Question

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]

Answer 1

R with ape package, 12 bytes

ape::getMRCA

Built-in. Called as ape::getMRCA(tree, c(node1, node2)).

Answer 2

Python 2, 155 151 bytes

def f(a,b,T):g=lambda U:U and(U[0]in[a,b]or T[0]in[a,b]or g(U[1])or g(U[2]));L,R=map(g,T[1:]);return(L and R)and T[0]or L and f(a,b,T[1])or f(a,b,T[2])

Try it online!

This assumes that nodes are defined as

[node_id, left_node, right_node]

as it seems silly to define the nodes as

[node_id, not_neccessarily_unique_node_value, left_node, right_node, parent_node]

because both the other_not_neccessarily_unique_node_value and parent_node are completely ignored in this problem.

The g function evaluates whether U is a ancestor of the nodes identified by either a or b.

Starting with the root node, if g is true of both the left child and the right child OR this node is either the a node_id or the b node_id, then this node is the LCA. Otherwise, exactly one of the two children - the left child or the right child - is then either the LCA or has the LCA as a child.

Answer 3

Ruby, 86 bytes

f=->t,x,y=p{t==x ?(!y||f[x,y])&&t:t&&(f[t.l,x,y]||f[t.r,x,y]||y&&(f[t,x]&&f[t,y])&&t)}

Try it online!

If I understand correctly, sorting by value isn't guaranteed and we're returning node references so the value isn't actually used for anything. We're just checking a node's l and r values to see if they contain x and y. The function returns a falsey value if either of the provided nodes isn't in the tree so that it can be called recursively.

Answer 4

Jelly, 15 13 bytes

œiⱮn/œpḢƊḢœị⁸

Try it online!

A dyadic link taking the tree as left argument and the two node ids as right argument. Returns the full node of the lowest common ancestor.

Node ids are floating point. On TIO I’ve used vaguely hierarchical ids, but the actual numbers are arbitrary.

Answer 5

Haskell, 72 70 bytes

a#b|let g t@(i:%c)=(g=<<c)++[i|t!a,t!b];(i:%c)!e=i==e||any(!e)c=head.g

The tree data structure is data T = (Int,Int) :% [T], i.e. a pair (<id>,<value>) and a list of child trees per node. Needs no link to parent within the node. Returns the (<id>,<value>) pair of the LCA.

Try it online!

Answer 6

Wolfram Language (Mathematica), 53 bytes

Head@#&@@Cases[{#},a_/;!a~FreeQ~#2&&!a~FreeQ~#3,∞]&

Try it online!

FirstCase seems to be traversing the tree in a different order than Cases...

Function which takes the tree and two node values, and returns the value of the lowest common ancestor.

Represents the tree as an expression, where the head contains the value, and uses Null (or anything else that is guaranteed to not be a node) to represent the absense of a leaf.

For the example tree given, the structure looks like this:

Answer 7

Charcoal, 38 bytes

Ｗ∧η⊞Ｏυη≔§⊟Φθ⁼§κ⁰η⁴ηＷ¬№υζ≔§⊟Φθ⁼§κ⁰ζ⁴ζＩζ

Try it online! Link is to verbose version of code. Takes input as a list of [id, value, leftid, rightid, parentid], where a 0 value means no id. Explanation:

Ｗ∧η⊞Ｏυη≔§⊟Φθ⁼§κ⁰η⁴η

Walk the tree up from the first input node id, saving the found ids in the predefined empty list.

Ｗ¬№υζ≔§⊟Φθ⁼§κ⁰ζ⁴ζ

Walk the tree up from the second input node id until one of the ids matches.

Ｉζ

Print the matching id. (If strings were acceptable as ids, the Ｉ would not be necessary, but if both strings and numbers had to be supported, then that would cost an extra byte.)

Answer 8

05AB1E, 10 bytes

ΔDʒ˜ÃQ}`}н

Try it online!

First input is a tree in the format described in this answer, because I have no idea how the format in the question is supposed to work. Second input is a pair of node ids.

Explanation:

Δ       }     # repeat until top of stack doesn't change
 Dʒ   }       #  filter a copy of tree by
   ˜          #   flatten
    Ã         #   list intersection with the second input
     Q        #   equals the second input
       `      #  dump all results on the stack
         н    # get the first element (the node id)