[DonaldPShimoda]

> That example isn't tail recursive, though.

Oh damn, you're completely right. My mistake! I guess I should've actually re-read my comment before linking here since they were about slightly different things haha. Oh well.

> The Python version is more difficult to read because you're using a manual stack instead of relying on the built-in one.

For a sufficiently large input, Python will error due to its maximum stack recursion depth (default is 1000, I think), so a generic solution requires using an in-language stack or else modifying your Python configuration to circumvent the maximum. (Or using a different language, I suppose.)

> The tail recursive Haskell version of your Python isn't much better

I do find that less readable than the non-tail-recursive version I had written previously, but still easier to read than the Python version with an explicit stack.

An alternative approach might be to use a zipper instead of a list, but that's probably (definitely) over-engineering the problem haha.

Actually for fun I put together a zipper-y solution. It takes a lot of scaffolding, but if we assume the zipper stuff was already implemented then the `sumTree` solution itself is nice enough:

    data BTree
      = Leaf Int
      | Branch Int BTree BTree
    
    data Path
      = Top
      | InLeft Int Path BTree
      | InRight BTree Int Path
    
    type Location = (BTree, Path)
    
    data Direction
      = Up
      | Down
    
    goDownLeft :: Location -> Location
    goDownLeft (Leaf _, _)       = error "down of Leaf"
    goDownLeft (Branch v l r, p) = (l, InLeft v p r)
    
    goDownRight :: Location -> Location
    goDownRight (Leaf _, _)       = error "down of Leaf"
    goDownRight (Branch v l r, p) = (r, InRight l v p)
    
    goUp :: Location -> Location
    goUp (_, Top)           = error "up of Top"
    goUp (l, InLeft v p r)  = (Branch v l r, p)
    goUp (r, InRight l v p) = (Branch v l r, p)
    
    sumTree :: BTree -> Int
    sumTree t = sumTree' Down (t, Top) 0
    
    sumTree' :: Direction -> Location -> Int -> Int
    sumTree' Down l r = case l of
      (Leaf v, _)        -> sumTree' Up l (v + r)
      _                  -> sumTree' Down (goDownLeft l) r
    sumTree' Up l r = case l of
      (_, Top)           -> r
      (_, InLeft{})      -> sumTree' Down (goDownRight (goUp l)) r
      (_, InRight _ v _) -> sumTree' Up (goUp l) (v + r)

I feel like there's maybe a way to implement this more efficiently (like with a better choice of zipper constructors), but I really don't have a ton of experience with zippers so this is what I came up with. Maybe you know a better way?