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.

About these ads

Pages: 1 2

26 Responses to “Lowest Common Ancestor”

  1. 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
    
  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
    succinct 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 ==/=).

  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 .
    Here is the link : http://codepad.org/Q5frvH8P

  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 .
    New link is at http://codepad.org/GKK9n6Td

  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 :

    http://codepad.org/m0U1KVje

  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) {
        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;
    }
    
  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: [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: