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


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.

Binary Tree 1

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.


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.


Assume there is a least common ancestor present for any two nodes in the binary tree.


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.


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;

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]

T. Salim

Posted 2019-08-15T16:47:07.997

Reputation: 575

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



R with ape package, 12 bytes


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

Robin Ryder

Posted 2019-08-15T16:47:07.997

Reputation: 6 625

Thanks R, for providing the first answer. – T. Salim – 2019-08-15T17:13:14.070


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.

Chas Brown

Posted 2019-08-15T16:47:07.997

Reputation: 8 959


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.


Posted 2019-08-15T16:47:07.997

Reputation: 20 600

You are right about your assumptions, histocrat. But I think I should add an assumption in the question making it clear that there is at least common ancestor present in the binary tree. – T. Salim – 2019-08-15T18:52:17.507

You can add that assumption, but recursive answers like this can't take advantage of it since they will encounter subtrees for which it no longer holds. – histocrat – 2019-08-15T18:54:32.240


Jelly, 15 13 bytes


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.

Nick Kennedy

Posted 2019-08-15T16:47:07.997

Reputation: 11 829


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!


Posted 2019-08-15T16:47:07.997

Reputation: 34 639


Wolfram Language (Mathematica), 53 bytes


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:

enter image description here


Posted 2019-08-15T16:47:07.997

Reputation: 3 495


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.)


Posted 2019-08-15T16:47:07.997

Reputation: 95 035


05AB1E, 10 bytes


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.


Δ       }     # 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)


Posted 2019-08-15T16:47:07.997

Reputation: 12 521