3
\$\begingroup\$

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.

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you provide exact input and output examples? Also, what if my programming language doesn't support references, pointers and structures? \$\endgroup\$ – Krzysztof Szewczyk Aug 15 at 17:18
  • 1
    \$\begingroup\$ If your language does not support references, you can use a list-like representation of a tree: [root_value, left_node, right_node, parent_node]. \$\endgroup\$ – T. Salim Aug 15 at 17:22
  • 1
    \$\begingroup\$ How 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). \$\endgroup\$ – Grimy Aug 19 at 15:59
4
\$\begingroup\$

R with ape package, 12 bytes

ape::getMRCA

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

\$\endgroup\$
  • \$\begingroup\$ Thanks R, for providing the first answer. \$\endgroup\$ – T. Salim Aug 15 at 17:13
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – T. Salim Aug 15 at 18:52
  • \$\begingroup\$ 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. \$\endgroup\$ – histocrat Aug 15 at 18:54
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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:

enter image description here

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 38 bytes

W∧η⊞Oυη≔§⊟Φθ⁼§κ⁰η⁴ηW¬№υζ≔§⊟Φθ⁼§κ⁰ζ⁴ζIζ

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:

W∧η⊞Oυη≔§⊟Φθ⁼§κ⁰η⁴η

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

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

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

Iζ

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

\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.