Haskell - Pretty Print Binary Tree - cannot fully get it to display in layers. Most code completed

Question

SOLUTION Thanks to Karolis Juodelė, here is my elegant solution to this problem! Thank you Karolis Juodelė :

prettyTree :: Show a=>BinTree a -> String
prettyTree Empty = ""
prettyTree (Node l x r) = prettyTree2((Node l x r),2)

prettyTree2 :: Show a=> (BinTree a, Int)-> String
prettyTree2 (Empty,_) = ""
prettyTree2 ((Node l x r),z) = prettyTree2(r,z+2) ++ replicate z ' ' ++ (show x) ++ ['\n'] ++ prettyTree2(l,z+2)

OLD So I am trying to print a binary tree like so:

putStr (prettyTree (Node (Node Empty 3 (Node Empty 7 Empty)) 8 (Node (Node Empty 8 Empty) 4 (Node Empty 3 Empty))))

      3
    4
      8
  8
      7
    3

What I have is the following which only prints them in two different lines:

data BinTree a = Empty | Node (BinTree a) a (BinTree a) deriving (Eq)

prettyTree :: Show a => BinTree a -> String
prettyTree Empty = ""
prettyTree (Node l x r) = prettyTree l ++ middle ++ prettyTree r
    where
        maxHeight = max (treeHeight l) (treeHeight r) + 1
        middle = printSpace (maxHeight, maxHeight) ++ show x ++ "\n"

treeHeight :: BinTree a -> Integer
treeHeight Empty = 0
treeHeight (Node l x r) = 1 + max (treeHeight l) (treeHeight r)

printSpace :: (Integer,Integer) -> String
printSpace (0, _) = []
printSpace (_, 0) = []
printSpace (x, y) = "   " ++ printSpace ((x `mod` y), y)

What I am trying to acomplish is that based on the total height of the tree, I will modulate the current height at the node, hence the root will be 0, then level 1 will be 1 and so fort.

I understand that I am actually passing the height twice for each level and I am not passing the total height of the tree. What can I do to actually get the total height of the tree for every level of the recursion?

Karolis Juodelė · Accepted Answer · 2013-10-06 08:33:13Z

2

Simply add another parameter to prettyTree. Something like padding :: Int. Then add replicate padding ' ' spaces to middle and pass padding + 2 to prettyTree of left and right subtrees.

Note, what you actually want is to define prettyTree t = paddedPrettyTree t 2 so as not to change the type of prettyTree.

answered Oct 6, 2013 at 8:33

Karolis Juodelė

3,7712 gold badges23 silver badges33 bronze badges

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

1 Comment

Georgi Angelov Over a year ago

AH!!! That was by far the simplest and easiest solution ever!! worked like a charm! I guess I was simply looking for exactly that - replicate - without even knowing it! Thank you!

Collectives™ on Stack Overflow

Haskell - Pretty Print Binary Tree - cannot fully get it to display in layers. Most code completed

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related