Programming Praxis – Lowest Common Ancestor

In today’s Programming Praxis exercise, our goal is to write an algorithm to find the lowest common ancestor of two nodes in a binary tree. Let’s get started, shall we?

First, we define a binary tree data structure.

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

The algorithm is pretty trivial: if the higher value is less than the current node, descend the left branch. If the lower value is higher than the current node, descend the right branch. Otherwise, we’ve found our result.

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

Some tests to see if everything is working properly:

main :: IO ()
main = do let tip n = Node n Nil Nil
          let tree = Node 8 (Node 3 (tip 1) (Node 6 (tip 4) (tip 7)))
                            (Node 10 Nil (Node 14 (tip 13) Nil))
          print $ lca 4  7 tree == 6
          print $ lca 4 10 tree == 8
          print $ lca 1  4 tree == 3
          print $ lca 1  3 tree == 3
          print $ lca 3  6 tree == 3

Yup. Simple enough.

Like this:

Be the first to like this post.

Tags: ancestor, binary, bonsai, code, common, Haskell, kata, lowest, praxis, programming, tree

This entry was posted on March 11, 2011 at 10:51 am and is filed under Programming Praxis. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

8 Responses to “Programming Praxis – Lowest Common Ancestor”

Mithrandir Says:
March 11, 2011 at 3:47 pm | Reply
You have a problem in your solution stemming from the fact that you supposed that node values give hints about the tree structure (and you decided what to call next by using the values).

See what happens when you change the 7 to a 17 without changing anything else (except the node value and the first test content).

Remco Niemeijer Says:
March 11, 2011 at 4:20 pm | Reply

Yes, I’m assuming the tree being used is a valid binary search tree since that is what is assumed in the Scheme solution. If you remove that assumption, the solution becomes less efficient since it has to search the entire tree:

import Control.Applicative

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

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

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

Graham Says:
March 11, 2011 at 8:22 pm | Reply
I’m always impressed with the elegance and brevity of your solutions. If you don’t mind my asking (as a Haskell newbie), what’s the significance of the tilde (~) in your definition of lca? Is it similar to the dollar sign ($), forcing evaluation of (Node v l r)?
Remco Niemeijer Says:
March 11, 2011 at 8:56 pm | Reply
I’m not sure what you mean by ($) forcing evaluation, since it doesn’t (for example, try evaluating const 1 $ undefined). I think you’re referring to ($!), which does force evaluation. As for the tilde, it makes the pattern irrefutable. It is used here to get rid of the compiler warning for not handling the Nil case. Reaching a Nil node would mean that the given elements are not in the tree, which means that there is no common ancestor. There are other ways of handling it, such as handling the Nil case with an explicit error message or changing the resulting type to Maybe a and returning Nothing, but since you’re only supposed to call the function with valid elements I decided to go with the more compact solution of not handling it (producing a pattern match failure if it is ever encountered).
Graham Says:
March 11, 2011 at 10:02 pm | Reply
Thanks for your answer (and clearing up my confusion).
Grégory LEOCADIE Says:
March 15, 2011 at 4:56 pm | Reply
Hi remco,
in the case, we assume that the tree is not a bineary search tree, if m is r and n is l, you have to return v, but in your solution it goes in the otherwise-branch. or am I missing something?
Remco Niemeijer Says:
March 15, 2011 at 5:13 pm | Reply
Hi Grégory,

You’re right. The condition should be
```
(has m (Node v l Nil) && has n (Node v Nil r)) ||
(has n (Node v l Nil) && has m (Node v Nil r))
```
since switching from a binary search tree to a binary tree removes the guarantee that m will be to the left of n.
Elvis Montero » Blog Archive » Lowest Common Ancestor Says:
March 21, 2011 at 11:59 pm | Reply
[...] That’s it! We don’t need anything else. A straightforward solution is possible in 3 steps. Can you do better? I recommend you read some of the solutions posted at PP. There are incredible implementations there (e.g. Remco’s amazing Haskell solution). [...]

Bonsai Code