CODEWITHSUNDEEP
haskellbinary-treetransformationtraversal
AwhatLoop
AwhatLoop

Reputation: 31

Haskell binary tree traversal

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.

Upvotes: 0

Views: 498

Answers (2)

Will Ness
Will Ness

Reputation: 71065

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 whole thing is linear,(*) 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.

(*)No spine is pulled from over more than once, because we are pulling from the tree which is already without any 0s, "after" the recursive call. So these will be another O(n) operations in total.

Upvotes: 0

Daniel Wagner
Daniel Wagner

Reputation: 152707

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.

Upvotes: 2

Related Questions