How do you return the smallest sub-tree which contains two nodes whose keys are given, in a BST?

Question

I defined a BST in Haskell:

data BST a = BST a (BST a) (BST a) | BSTNil deriving Show

and some operations like these:

findElem :: (Ord a, Eq a) => BST a -> a -> Maybe a
findElem BSTNil _ = Nothing
findElem (BST a left right) x
        | x == a = Just x
        | x < a = findElem left x
        | x > a = findElem right x

inorder :: BST a -> [a]
inorder BSTNil = []
inorder (BST a left right) = inorder left ++ [a] ++ inorder right

How am I supposed to return the smallest sub-tree which contains two nodes whose keys are given, of a BST?

That's what I got so far:

subTree :: (Ord a, Eq a) => BST a -> a -> a -> Maybe (BST a)
subTree BSTNil _ _ = Nothing
subTree (BST a left right) x y 
     | findElem (BST a left right) x == Nothing = Nothing
     | findElem (BST a left right) y == Nothing = Nothing
     | findElem left x /= Nothing && findElem left y /= Nothing = subTree 
                                                                  left x y
     | findElem right x /= Nothing && findElem right y /= Nothing = subTree 
                                                                    right x y

Answer 1

Just enumerate the cases, there are not that many:

• both values must be found in the left subtree, then return the recursive result from that
• one (or both) values match the current value, then try to find the other and if found return the current node
• the smaller value must be found in the left subtree and the larger value must be found in the right subtree, then try to find them and if both are found return the current node
• both values must be found in the right subtree, then return the recursive result from that

To distinguish these cases, you should only compare a, x and y, not use findElem, just like you did to distinguish the three cases in the findElem function. (You may call findElem though if you need to find a single element in a subtree). So I'd do

subTree :: (Ord a, Eq a) => BST a -> a -> a -> Maybe (BST a)
subTree BSTNil _ _ = Nothing
subTree t@(BST a left right) x y
     | x < a && y < a = subTree left x y
     | x == a         = findElem t y *> Just t
     | y == a         = findElem t x *> Just t
     | x > a && y > a = subTree right x y
     | otherwise      = findElem t y *> findElem t x *> Just t -- x < a < y or y < a < x

(As @Will Ness mentioned, you might simplify if you know - or force - that x <= y)