haskellfunctional-programmingbinary-search-treesubtree

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


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

Solution

  • Just enumerate the cases, there are not that many:

    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)