Splitting a BinTree with tail recursion in Haskell

Question

So this week we learned about union types, tail recursion and binary trees in Haskell. We defined our tree data type like so:

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

leaf :: a -> BinTree a
leaf x = Node Empty x Empty

Now we were asked to write a function to find the most left node, return it, cut it out and also return the remaining tree without the node we just cut.

We did something like this, which worked quite well:

splitleftmost :: BinTree a -> Maybe (a, BinTree a)
splitleftmost Empty = Nothing
splitleftmost (Node l a r) = case splitleftmost l of
                                 Nothing -> Just (a, r)
                                 Just (a',l') -> Just (a', Node l' a r)

Now I need to make this function tail recursive. I think I understood what tail recursion is about, but found it hard to apply it to this problem. I was told to write a function which calls the main function with the fitting arguments, but was still not able to solve this.

Answer 1

Since nodes do not have a parent link, one approach would be to maintain root-to-leaf path within a list. At the end the modified tree can be constructed using a left fold:

slm :: BinTree a -> Maybe (a, BinTree a)
slm = run []
    where
    run _ Empty = Nothing
    run t (Node Empty x r) = Just (x, foldl go r t)
        where go l (Node _ x r) = Node l x r

    run t n@(Node l _ _) = run (n:t) l