0

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.

Improve this question
20
  • 1
    Suppose in your drawing, the root node 5 were 0, and the current 0s were 5. What tree would you want to see come out of modTree? Commented Sep 28, 2021 at 14:37
  • 1
    @DanielWagner Then I do not understand the description. OP, can you please post a sample input/output for a case where the 0 subtrees are not leaves? Commented Sep 28, 2021 at 14:46
  • 1
    @EugeneSh. Right. And now maybe you can see why I asked the question I did. ^_^ Commented Sep 28, 2021 at 14:47
  • 1
    In your update you a) Do not show the correct output, b) contradicting your comment about zeros being only leaves. Commented Sep 28, 2021 at 14:54
  • 1
    @AwhatLoop I asked my question (about swapping 5 and 0) very carefully. Please answer the question I asked, not a different question. In my question, the input tree has two 5 nodes: 0 at the root, left tree is (4 at the root, 5 to the left, 1 to the right) and right tree is 5. Commented Sep 28, 2021 at 14:55

2 Answers 2

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Challenge problem: what is the time complexity of this algorithm? It's obviously O(n^2); is it also O(n)? I've attempted to create a pathological input that achieves n^2 work in a couple different ways and they've all actually only required linear work -- but this may just mean I'm having a failure of imagination! I can't see how to prove that it's always linear. The trouble with achieving n^2 seems to be that you want to have a lot of 0s for that, but if you have a lot of 0s, then your recursive call makes a very small tree and bubbling doesn't take much work.
...ah, got it. A left-spine-only tree with alternating 0s and 1s requires θ(n^2) work.
I like this approach, but I'm still having the issue of how to recursively go through the tree. In other languages, it would be: postorder(Node) { if (Node != null) { postorder(left_child) postorder(right_child) visit Node } } But I don't get how this works in Haskell
@AwhatLoop In Haskell, you write postorder Void = ...; postorder (Node left_child node right_child) = visit node (postorder left_child) (postorder right_child). Not so different, really, though "postorder" becomes a bit stranger of a name when the evaluation order is more fluid. (It was already strange because it didn't mention what visit was intended to do at all; now it's even stranger.)
Ohh I just grabbed a textbook example of postorder. "visit" was just a line to explain an action at the node.
|
0

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.

Improve this answer

5 Comments

Nice! This can even be made nicely lazy by hoisting each element of the right spine up one level, rather than hoisting the last element of the right spine up many levels.
yeah, I know they said the order doesn't matter but still it's nice to preserve it as much as possible, I thought... old habits, all that <s>cra</s>jazz. nice idea.
Ah, and the nicely lazy version also has a very nice proof of linear-time execution. Instead of thinking of hoisting, continue to think in terms of bubbling zeros down. The algorithm is equivalent to, for each zero, bubbling down left once, then down right until a leaf. No two zeros bubble down right across the same edge. There are a linear number of edges, so a linear number of right bubbles; and a linear number of zeros, so a linear number of left bubbles. Done!
so, to recap: because no spine is ever pulled from twice, it's all linear. both for my version and your refinement of it. (because the pulling happens over the result of the recursive call, which has no 0s in it anymore). as to laziness, your "lazier" way might be lazier under preorder traversal of the resulting tree, but my way could actually be lazier under inorder traversal. I think.
Ah, good point about traversal order!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.