Lowest Common Ancestor
March 11, 2011
We begin with the minimal code needed to insert elements in a binary tree:
(define (tree k l r) (vector k l r))
(define (key t) (vector-ref t 0))
(define (lkid t) (vector-ref t 1))
(define (rkid t) (vector-ref t 2))
(define nil (vector 'nil 'nil 'nil))
(define (nil? t) (eq? t nil))
(define (lookup lt? t k)
(cond ((nil? t) #f)
((lt? k (key t)) (lookup lt? (lkid t) k))
((lt? (key t) k) (lookup lt? (rkid t) k))
(else #t)))
(define (insert lt? t k)
(cond ((nil? t) (tree k nil nil))
((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t)))
((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k)))
(else (tree k (lkid t) (rkid t)))))
Given that, the tree shown on the previous page can be built with the following statements:
(define t nil)
(set! t (insert < t 8))
(set! t (insert < t 3))
(set! t (insert < t 10))
(set! t (insert < t 1))
(set! t (insert < t 6))
(set! t (insert < t 14))
(set! t (insert < t 4))
(set! t (insert < t 7))
(set! t (insert < t 13))
The lowest common ancestor is the first node on which the two desired elements are on opposite sides; if both elements are less than the current key, descend the left sub-tree and try again, if both elements are greater than the current key, descend the right sub-tree and try again, otherwise the current node is the desired result. The only trick is to branch the right way on equality; that long first condition is just lo ≤ (key t) ≤ hi, but since we only have lt? it looks odd:
(define (lca lt? t lo hi)
(cond ((and (not (lt? (key t) lo))
(not (lt? hi (key t)))) (key t))
((lt? (key t) lo) (lca lt? (rkid t) lo hi))
(else (lca lt? (lkid t) lo hi))))
Here are some tests:
(display (lca < t 4 7)) (newline) ; 6
(display (lca < t 4 10)) (newline) ; 8
(display (lca < t 1 4)) (newline) ; 3
(display (lca < t 1 3)) (newline) ; 3
(display (lca < t 3 6)) (newline) ; 3
You can run the code at http://programmingpraxis.codepad.org/h8u1RuTR.
Programming Praxis 
My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/11/programming-praxis-lowest-common-ancestor/ for a version with comments):
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@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?
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.
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.
@Serabe: Correct me if i am wrong , I think order is implicit for binary trees , say isAncestor relation ship.
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.
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 rFirst, 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’ssuccinct Haskell code.
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 ==/=).
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)
Ok formatting does not seem to work .
Here is the link : http://codepad.org/Q5frvH8P
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
Just ignore my previous post , all binary tree are ordered, thats it period.
Sorry for spamming , this is last post for today.
I have slightly modified and commented my previous code .
New link is at http://codepad.org/GKK9n6Td
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)))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
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 bSolution in Perl: http://pastebin.com/r22zy559
Boy, do I need to learn Ocaml/F#.
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.
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.
@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.
This one number the nodes of binary tree and uses Remco Niemeijer’s code (first post)
to compute the LCA :
http://codepad.org/m0U1KVje
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) { add(&(*root)->left, value); } else add(&(*root)->right, 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; add(&root, 8); add(&root, 3); add(&root, 10); add(&root, 1); add(&root, 6); add(&root, 14); add(&root, 4); add(&root, 7); add(&root, 13); 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; }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 NoneOops. 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.
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][…] Yet another PP challenge piqued my interest. Here’s the problem statement: […]