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.

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 599 other followers

%d bloggers like this: