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.

About these ads

Tags: , , , , , , , , , ,

8 Responses to “Programming Praxis – Lowest Common Ancestor”

  1. Mithrandir Says:

    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).

  2. Remco Niemeijer Says:

    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
    
  3. Graham Says:

    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)?

  4. Remco Niemeijer Says:

    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).

  5. Graham Says:

    Thanks for your answer (and clearing up my confusion).

  6. Gr├ęgory LEOCADIE Says:

    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?

  7. Remco Niemeijer Says:

    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.

  8. Elvis Montero » Blog Archive » Lowest Common Ancestor Says:

    [...] 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). [...]

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

%d bloggers like this: