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.