Printing Binary Tree per Layer in a List

Question

The function should print the markings of the argument tree in layers as a list of layers. The node and leaf markings in each layer are listed from left to right, that is, which is the most left node of the layer, the first element of the list, the right-most node is the last element of the list. The argument of type Ord indicates whether the layers in ascending order from the smallest to the largest layer (TopDown) or in descending order from largest to smallest layer (BottomUp) are to be issued

data Tree = Leaf Integer | Node Integer Tree Tree

type Layer = [Integer]

data Ord = BottomUp | TopDown

wLayer :: Tree -> Ord -> [Layer] 

Example 1: We call the function wLayer with arguments
wLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) TopDown the result : [[1],[2,3],[21,22,31,32]]

Example 2: wLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) BottomUp the result: [[21,22,31,32],[2,3],[1]]

how can i implement this one ?

Edit

data Tree = Leaf Integer
          | Node Integer Tree Tree
type Layer = [Integer]
data Ord   = BottomUp | TopDown

writeLayer :: Tree -> Ord -> [Layer]
writeLayer Leaf x = [x]
writeLayer (Node x lt rt) BottomUp = (writeLayer rt BottomUp) ++ [x] ++ (writeLayer lt BottomUp)
writeLayer (Node x lt rt) TopDown  = [x] ++ (writeLayer lt TopDown) ++ (writeLayer rt TopDown)

this is my program but it isn't work how can i fix it ?

Answer 1

Here is a simple way of accomplishing this. It takes all of the nodes at a level and extracts the integer value from them, and then recurses on all of the children of these same nodes. After that, you match on Ord to determine if you need to reverse the list.

writeLayer t o =
    case o of
        BottomUp -> reverse $ makeLayer [t]
        TopDown -> makeLayer [t]
    where
        extract (Node i _ _) = i
        extract (Leaf i) = i
        children (Node _ a b) = [a, b]
        children _ = []
        makeLayer [] = []
        makeLayer ts = map extract ts : (makeLayer $ concat $ map children ts)

Answer 2

Some hints:

• the case where the Tree is a Leaf is trivial
• the difference between BottomUp and TopDown seems to be whether you reverse the list of Layers
• when the Tree is a Node you will have to recurse on the subtrees and combine the results somehow

Edit: OK, let's concentrate on the first of these.

The equation you have for this case is

writeLayer Leaf x = [x]

First, the Leaf x needs to be in parentheses, because it's a single Tree value.

writeLayer (Leaf x) = [x]

Second, the equation needs to reflect that writeLayer takes two parameters (as written above, it takes only one). With a Leaf value, we don't care which order the results are to be returned in --- we give the same answer either way --- but we still have to take the parameter. We use _ to signal that we don't care above the parameter and aren't going to use it.

writeLayer (Leaf x) _ = [x]

Thirdly, [x] is a (single element) list of Integers --- but we are supposed to be returning a list of Layers. I'm sure you can figure out how to fix this.

Finally, pay attention to the error messages the computer gives you. Understand them.

Answer 3

Paul's answer gives a corecursive definition of level-order traversal - an unfold to lists. (Exercise: write makeLayer using Data.List.unfoldr.) That's my favourite way too; see The Underappreciated Unfold.

But it can also be done recursively - as a fold on trees. These are defined by analogy with foldr on lists as follows:

foldt :: (Integer->a) -> (Integer->a->a->a) -> Tree -> a
foldt f g (Leaf n)     = f n
foldt f g (Node n t u) = g n (foldt f g t) (foldt f g u)

Then level-order traversal is given by a straightforward tree fold, with a possible reverse:

wLayer :: Tree -> Order -> [Layer] 
wLayer t o = (if o==BottomUp then reverse else id) (foldt single glue t)

I took the liberty of renaming your flag type Order to a void a name clash, and making it an instance of Eq:

data Order = BottomUp | TopDown deriving Eq

The function single makes the level-order traversal of a leaf:

single :: Integer -> [Layer]
single n = [[n]]

whereas glue combines a label and the traversals of two children into the traversal of a node:

glue :: Integer -> [Layer] -> [Layer] -> [Layer]
glue n x y = [n] : longzipwith (++) x y

The crucial ingredient is a function longzipwith, which is like zipWith except that (i) the length of the result is the length of the longer argument, not the shorter, and hence (ii) the binary operator has to be a->a->a:

longzipwith :: (a->a->a) -> [a] -> [a] -> [a]
longzipwith f (a:x) (b:y) = f a b : longzipwith f x y
longzipwith f x     []    = x
longzipwith f []    y     = y

Answer 4

this is my program yet

data Tree = Leaf Integer
    | Node Integer Tree Tree
type Layer = [Integer]
data DOrd   = BottomUp | TopDown
writeLayer :: Tree -> DOrd -> [Integer]
writeLayer (Leaf x) _ = [x]
writeLayer (Node x lt rt) BottomUp = (writeLayer rt BottomUp) ++ [x] ++ (writeLayer lt BottomUp)
writeLayer (Node x lt rt) TopDown  = [x] ++ (writeLayer lt TopDown) ++ (writeLayer rt TopDown)

Calls:

*Main> writeLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) TopDown
[1,2,21,22,3,31,32]
*Main> writeLayer (Node 1 (Node 2 (Leaf 21) (Leaf 22)) (Node 3 (Leaf 31) (Leaf 32))) BottomUp
[32,3,31,1,22,2,21]

but i want to take first : [[1],[2,3],[21,22,31,32]]

second : [[21,22,31,32],[2,3],[1]]