## Lowest Common Ancestor

### March 11, 2011 Today’s problem appears with some regularity at places like Proggit and Stack Overflow and in lists of programming interview questions:

Given a binary tree t and two elements of the tree, m and n, with m<n, find the lowest element of the tree (farthest from the root) that is an ancestor of both m and n.

For example, in the tree shown at right, the lowest common ancestor of 4 and 7 is 6, the lowest common ancestor of 4 and 10 is 8, and the lowest common ancestor of 1 and 4 is 3. It is possible for an element of the tree to be its own ancestor, so the lowest common ancestor of 1 and 3 is 3, and the lowest common ancestor of 3 and 6 is 3.

Your task is to write a function that finds the lowest common ancestor of two elements of a binary tree. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 26 Responses to “Lowest Common Ancestor”

```data BinTree a = Node a (BinTree a) (BinTree a) | Nil

lca :: Ord a => a -> a -> BinTree a -> a
lca m n ~(Node v l r) | n < v     = lca m n l
| m > v     = lca m n r
| otherwise = v
```
2. Serabe said

@Remco: how does that work in a binary tree that is not a binary search tree?
@ProgrammingPraxis: did you mean binary tree or binary search tree?

3. programmingpraxis said

Serabe: I’m not sure I know the difference between a binary tree and a binary search tree. The trees we are talking about have nodes with two children, all nodes with keys less than the current node in the left child and all nodes with keys greater than the current node in the right child.

4. Serabe said

That’s a binary search tree. A tree whose nodes have two children are binary trees (without the order restriction). I guess you can see now that Remco’s algorithm cannot work on binary trees, without the “search” part.

5. Veer said

@Serabe: Correct me if i am wrong , I think order is implicit for binary trees , say isAncestor relation ship.

6. F. Carr said

http://en.wikipedia.org/wiki/Binary_tree — including the statement “Binary trees are used to implement binary search trees and binary heaps.”

http://en.wikipedia.org/wiki/Binary_search_tree

The LCA problem is interesting in both cases. With a binary *search* tree, one can use a more-specialized more-efficient algorithm.

7. Here’s a version for binary trees that are not binary search trees. It is of course less efficient than the original since it now has to search the entire tree.

```import Control.Applicative

data BinTree a = Node a (BinTree a) (BinTree a) | Nil deriving (Eq, Show)

has :: Eq a => a -> BinTree a -> Bool
has _ Nil = False
has e (Node v l r) = v == e || has e l || has e r

lca :: Ord a => a -> a -> BinTree a -> Maybe a
lca _ _ Nil = Nothing
lca m n (Node v l r) | has m (Node v l Nil) && has n (Node v Nil r) = Just v
| otherwise = lca m n l <|> lca m n r
```
8. Graham said

First, a Python version. My `insert()` method is a bit cumbersome,
since it checks whether the current node has a left/right subtree before
heading down it. I owe the `lca()` implementation to Remco’s

```class BST(object):
def __init__(self, val=None, right=None, left=None):
self.val = val
self.right = right
self.left = left
return None

def __nonzero__(self):
return self.val is not None

def insert(self, item):
if not self:
self.val = item
elif item < self.val:
if self.left:
return self.left.insert(item)
else:
self.left = BST(val=item)
elif item > self.val:
if self.right:
return self.right.insert(item)
else:
self.right = BST(val=item)
return None

def lca(self, m, n):
if n < self.val:
return self.left.lca(m, n)
elif m > self.val:
return self.right.lca(m, n)
else:
return self.val

if __name__ == "__main__":
b = BST()
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
b.insert(k)
for pair in [(4, 7), (4, 10), (1, 4), (1, 3), (3, 6)]:
print b.lca(*pair)
```

I’m also trying to learn Common Lisp with the help of Paul Graham’s “Ansi
Common Lisp;” here’s a Common Lisp attempt:

```(defstruct (node) val (left nil) (right nil))

(defun insert (bst obj)
(cond ((null bst) (make-node :val obj))
((= (node-val bst) obj) bst)
((> (node-val bst) obj)
(make-node
:val     (node-val bst)
:left    (insert (node-left bst) obj)
:right   (node-right bst)))
(t
(make-node
:val    (node-val bst)
:left   (node-left bst)
:right  (insert (node-right bst) obj)))))

(defun lca (bst m n)
(let ((v (node-val bst)) (l (node-left bst)) (r (node-right bst)))
(cond ((and (not (null l)) (< n v)) (lca l m n))
((and (not (null r)) (> m v)) (lca r m n))
(t v))))

(setf b nil)

(dolist (n '(8 3 10 1 6 14 4 7 13))
(setf b (insert b n)))

(dolist (x '((4 . 7) (4 . 10) (1 . 4) (1 . 3) (3 . 6)))
(print (lca b (car x) (cdr x))))

(princ #\newline)
```

Both versions assume we’re working with a binary search tree with only numbers
in it (or at least objects that can be compared with ==/=).

9. Veer said

If we are not allowed to use comparison operator , and if it is not necessary
that m < n , then this program might work , but i don't know how efficient it is?

#lang racket

(define-struct binary-tree (root left right))

(define immediate-ancestor (make-hash))

(define (make-ancestor tree ancestor)
(cond
[(empty? tree) (void)]
[else (hash-set! immediate-ancestor (binary-tree-root tree) ancestor)
(make-ancestor (binary-tree-left tree) (binary-tree-root tree))
(make-ancestor (binary-tree-right tree) (binary-tree-root tree))]))

(define (get-ancestor k)
(hash-ref immediate-ancestor k #f))

(define (get-common m n)

(define mark-visited (make-hash))

(define (set-path-m m)
(let ([ancestor (get-ancestor m)])
(hash-set! mark-visited m #t)
(unless (equal? ancestor m)
(set-path-m ancestor))))

(define (get-common1 n)
(let ([ancestor (get-ancestor n)])
(if (hash-ref mark-visited n #f)
n
(get-common1 ancestor))))

(set-path-m m)
(get-common1 n))

(define btree
(make-binary-tree
8
(make-binary-tree
3
(make-binary-tree 1 empty empty)
(make-binary-tree
6
(make-binary-tree 4 empty empty)
(make-binary-tree 7 empty empty)))
(make-binary-tree
10
empty
(make-binary-tree
14
(make-binary-tree
13
empty
empty)
empty))))

(make-ancestor btree (binary-tree-root btree))

(get-common 4 7)
(get-common 4 10)
(get-common 1 4)
(get-common 1 3)
(get-common 3 6)

10. veer said

Ok formatting does not seem to work .

11. Veer said

One Correction :
Is-Ancestor relationship example i gave is not right in the current context.

Discrete structure book that i have defines binary tree to be a ordered tree.
Wikipedia does not say that it has to be ordered, i wonder which one is correct.

If all the elements of binary tree are distinct then i guess we could easily define
the ordering.

cheers

12. Veer said

Just ignore my previous post , all binary tree are ordered, thats it period.
Sorry for spamming , this is last post for today.

13. Veer said

I have slightly modified and commented my previous code .

14. Jan Van lent said

Common Lisp solution for general binary tree (represented using lists).

```(defun tree-emptyp (tree) (null tree))
(defun node-value (tree) (first tree))
(defun node-left (tree) (second tree))
(defun node-right (tree) (third tree))

(defun ancestors (tree m &optional path)
(if (tree-emptyp tree)
nil
(let* ((val (node-value tree))
(path (cons val path)))
(if (eql val m) (reverse path)
(or (ancestors (node-left tree) m path)
(ancestors (node-right tree) m path))))))

(defun last-common (xs ys &optional default)
(cond ((null xs) default)
((null ys) default)
((eql (first xs) (first ys)) (last-common (rest xs) (rest ys) (first xs)))
(t default)))

(defun lowest-common-ancestor (tree m n)
(last-common (ancestors tree m) (ancestors tree n)))

;;; test

(defvar t1 '(8
(3 (1 nil nil) (6 (4 nil nil) (7 nil nil)))
(10 nil (14 (13 nil nil) nil))))

(defun test ()
(list (= (lowest-common-ancestor t1 4 10) 8)
(= (lowest-common-ancestor t1 1 4) 3)
(= (lowest-common-ancestor t1 3 6) 3)))
```
15. Khanh Nguyen said

In F#

type BTree =
| Empty
| Node of BTree * int * BTree

let rec lowest_common_ancestor (tree: BTree) (a: int) (b: int) =
match tree with
| Empty -> failwith "Wrong input"
| Node (l, n, r) -> if a <= n && n <= b then n
elif a < n && b < n then lowest_common_ancestor l a b
else lowest_common_ancestor r a b

16. Khanh Nguyen said
```
type BTree =
| Empty
| Node of BTree * int * BTree

let rec lowest_common_ancestor (tree: BTree) (a: int) (b: int) =
match tree with
| Empty          -> failwith "Wrong input"
| Node (l, n, r) -> if a <= n && n <= b then n
elif a < n && b < n then lowest_common_ancestor l a b
else  lowest_common_ancestor r a b
```
17. Josh said

Solution in Perl: http://pastebin.com/r22zy559

Boy, do I need to learn Ocaml/F#.

18. Maurits said

In the general “binary tree” case (where the tree is not necessarily a search tree) a naive approach is just finding the first common element of two lists:

ancestors_of_a = …
ancestors_of_b = …

most_recent_common_ancestor = first_common_element(ancestors_of_a, ancestors_of_b)

It would be interesting to see if there is a better algorithm for general binary trees.

19. My approach focuses on traversing the tree using DFS, saving each node’s path from the root, and then comparing the nodes’ path in order to find the lowest common ancestor. Here’s the Java function that traverses the tree:

```    static void traverse(Node node, Stack<Node> stack){
stack.push(node);

if(node.getRight() != null)
traverse(node.getRight(), stack);

if(node.getLeft() != null)
traverse(node.getLeft(), stack);

StringBuilder path = new StringBuilder();
for(Node n : stack)
path.append(n).append(" ");
node.setPath(path.toString().trim());

stack.pop();
return;
}
```

Here’s the function that finds the lowest common ancestor:

```    static String getLowestCommonAncestor(Node m, Node n){
String longerPath  = (m.getPath().length() > n.getPath().length()) ? m.getPath() : n.getPath();
String shorterPath = (longerPath.equals(m.getPath())) ? n.getPath() : m.getPath();

String[] lpElements  = longerPath.split(" ");
String[] spElements  = shorterPath.split(" ");

String lowest = "";
for(int i = 0; i < spElements.length; i++)
if(spElements[i].equals(lpElements[i]))
lowest = spElements[i];

return lowest;
}
```

The entire implementation can be seen here.

20. Veer said

@Maurits : If there exist a efficient algorithm for binary search tree ,
then same algorithm can be used for any binary tree, just number them accordingly.

21. Veer said

This one number the nodes of binary tree and uses Remco Niemeijer’s code (first post)
to compute the LCA :

22. Yuushi said

Here’s a solution in good old fashioned C:

```
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

struct btree {
int value;
struct btree *left, *right;
};

void add(struct btree **root, int value);
struct btree *find_lca(struct btree *root, int m, int n);

void add(struct btree **root, int value)
{
if(*root == NULL) {
*root = (struct btree *)malloc(sizeof(struct btree));
(*root)->left = (*root)->right = NULL;
(*root)->value = value;
}

else if((*root)->value > value) {
}

}

struct btree *find_lca(struct btree *root, int m, int n)
{
if(m <= root->value && n >= root->value) {
return root;
}
else if(m < root->value && n < root->value) {
return find_lca(root->left, m, n);
}
else return find_lca(root->right, m, n);
}

int main(void)
{
struct btree *root = NULL;
struct btree *lca = NULL;

lca = find_lca(root, 4, 7);
assert(lca->value == 6);
lca = find_lca(root, 4, 10);
assert(lca->value == 8);
lca = find_lca(root, 1, 4);
assert(lca->value == 3);
lca = find_lca(root, 1, 3);
assert(lca->value == 3);
lca = find_lca(root, 3, 6);
assert(lca->value == 3);

return 0;
}
```
23. Mike said

Python version that subclasses the list built-in type, and adds ‘insert’ and ‘lca’ methods.

Items are stored in the list such that for any self[ndx], self[2*ndx+1] is the root of the left subtree (items self[ndx]).

```class Bar(list):

def __init__(self, item=None):
list.__init__(self, (item, ))

def insert(self, item):
ndx = 0
while self[ndx] is not None:
ndx = 2*ndx + (1 if item < self[ndx] else 2)
if ndx >= len(self):
self.extend([None]*(ndx - len(self) + 1))
self[ndx] = item

def lca(self, lesser, bigger):
ndx = 0
while ndx < len(self) and not (lesser <= self[ndx] <= bigger):
ndx = 2*ndx + (1 if bigger < self[ndx] else 2)

return self[ndx] if ndx < len(self) else None

```
24. Mike said

Oops. Tried using < and > symbols in the test.

Anyway, for an item at index n, the left/right subtrees are rooted at 2n+1 and 2n+2, respectively.

25. Mike said

Given the same list structure in my previous post, the following lca()-function finds the lowest common ancestor for any two nodes regardless of whether the items in the tree are sorted, i.e., for any binary tree. The only requirement is that for an item at list[n], the two children are at list[2n+1] and list[2n+2].

```def lca(self, item1, item2):
ndx1 = y.index(item1)
ndx2 = y.index(item2)

while ndx1 != ndx2:
if ndx1 > ndx2:
ndx1 = (ndx1 - 1)/2
else:
ndx2 = (ndx2 - 1)/2

return self[ndx1]
```
26. […] Yet another PP challenge piqued my interest. Here’s the problem statement: […]