I am struggling with how to recursively traverse a binary tree in Haskell

It is rather clear how it's done when the return type is a list. But I don't get how is it done if the return type is a tree itself?

for example, if we have the tree and wish to exclude zeros:

                 5
                / \
               0   2
              / \
             0   1

and we would like to return a tree with the other numbers:

                 5
                / \
               1   2

Then I figured you would do something like this:

modTree :: Tree -> Tree
modTree Void = Void
modTree (Node l x r)
    | x == 0 = modTree l
    | otherwise = Node (modTree l) x (modTree r)

My issue is that I know that this will only traverse the left side. But I fail to grasp how recursively call the function in Haskell for the entire tree.

Any suggestions would be highly appreciated.

CodePudding user response：

One idea would be to bubble 0s down and left until they have no left child, then replace them with their right child. For example:

    0          1          1          1
   / \        / \        / \        / \
  1   2  ->  0   2  ->  3   2  ->  3   2
 / \        / \        / \          \
3   4      3   4      0   4          4

You need to take some care about what happens when there are multiple 0s on the path from root to leaf.

    0
   / \
  0   2
 / \
3   4

Probably the simplest (though perhaps not the most efficient) way to deal with this is to recursively drop 0s from the left child before beginning to bubble down.

    0          0          0          3          3
   / \        / \        / \        / \        / \
  0   2  ->  3   2  ->  3   2  ->  0   2  ->  4   2
 / \        / \          \          \
3   4      0   4          4          4

I encourage you to take a stab at implementing this yourself. If you have trouble, describing what you tried, where you got stuck, and why you think the problem you're seeing is insurmountable would make a good follow-up question.

CodePudding user response：

The standard thing to do here is this:

1. if the root is non-zero we apply the algorithm recursively to each of its child branches and we're done (as you already indicate in your code)
2. if the root is zero with only one child we just return that child (transformed, of course)
3. if the root is zero with two child branches we apply the algorithm recursively to each of the two branches, then pull the rightmost value from the new left child and put it into the root.

To pull the rightmost value from a tree:

1. if it's a leaf, just remove the leaf
2. if it's a node, it doesn't have a right child, so just put its left child in its place

The pull algorithm seems to be O(log n), thus making the whole thing linearithmic, apparently.

modTree :: Tree -> Tree
modTree Void = Void
modTree (Node l x r)
    | x == 0 = modZero (modTree l)   (modTree r)
    | otherwise = Node (modTree l) x (modTree r)

modZero Void r = r
modZero l Void = l
modZero l r = let (v, nl) = pullRightmost l in
  Node nl v r

Implementing pullRightmost is left as an exercise.