Displaying binary tree in Haskell

Question

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

I'm trying to figure out a way to display a binary tree in a manner such that for each level I go down in the tree, I want to add an additional * next to the name of the node and have them all separated by \n.

For example:

let x = Node "Parent" (Node "childLeft" (Node "grandChildLeftLeft" Emp Emp) Emp) (Node "childRight" Emp Emp)
putStrLn $ displayTree x

should return:

"Parent"
*"childLeft"
**"grandChildLeftLeft"
*"childRight"

My function (only prints up to one *):

displayTree :: Show a => BinTree a -> String
displayTree Emp = ""
displayTree (Node head Emp Emp) = (show head)
displayTree (Node head left Emp) = (show head) ++ "\n*" ++ displayTree left
displayTree (Node head Emp right) = (show head) ++ "\n*" ++ displayTree right
displayTree (Node head left right) = (show head) ++ "\n*" ++ displayTree left ++ "\n*" ++ displayTree right

My displayTree function would print:

"Parent"
*"childLeft"
*"grandChildLeftLeft"
*"childRight"

I want "grandChildLeftLeft" to have ** next to it instead of just *.

Any suggestions?

NOTE: I don't want to change the parameters that are passed into the function, so it should stay as displayTree :: Show a => BinTree a -> String

kvanbere · Accepted Answer · 2014-03-10 02:45:29Z

3

I think this is what you want:

module Main (main) where

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

showTree :: Show a => BinTree a -> Int -> String
showTree (Empty) _ = []
showTree (Node t l r) n = replicate n '*' ++ show t ++ "\n" ++ showTree l (n+1) ++ showTree r (n+1)

main :: IO ()
main = do
    let x = Node "Parent" (Node "childLeft" (Node "grandChildLeftLeft" Empty Empty) Empty) (Node "childRight" Empty Empty)
    putStrLn $ showTree x 0

Note the accumulator n which changes the indent level with each recursive call.

http://ideone.com/lphCoV

"Parent"
*"childLeft"
**"grandChildLeftLeft"
*"childRight"

edited Mar 10, 2014 at 2:45

answered Mar 10, 2014 at 2:29

kvanbere

3,3823 gold badges30 silver badges54 bronze badges

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

4 Comments

cactus1 Over a year ago

Ah, better use of Haskell than my answer, but two minor typos :). I'm pretty sure the end of your function should be showTree r (n+1) instead of showTree l (n+2)

kvanbere Over a year ago

Oops, had it in my head as a regular tree.

aanrv Over a year ago

I should have mentioned this earlier but I wanted to do this in a way that I would not have to change the parameters my display function would take.

kvanbere Over a year ago

You can copy showTree and move it into a where which you call with 0 so the original function still has the same parameters.

cactus1 · Accepted Answer · 2014-03-10 02:36:19Z

Why not pass in the depth to the displayTree function?

displayTree :: Show a => BinTree a -> String 
displayTree = displayTree' ""

displayTree' str Emp = ""
displayTree' str (Node head Emp Emp) = str ++ (show head)
displayTree' str (Node head left Emp) = str ++ (show head) ++ "\n" ++ displayTree' (str ++ "*") left
displayTree' str (Node head Emp right) = str ++ (show head) ++ "\n" ++ displayTree' (str ++ "*") right
displayTree' str (Node head left right) = str ++ (show head) ++ "\n" ++ displayTree' (str ++ "*") left ++ "\n" ++ displayTree (str ++ "*") right

Also, here's it refactored to be kinda more readable:

displayTree :: Show a => BinTree a -> String 
displayTree = displayTree' ""

displayTree' str Empty = ""
displayTree' str (Node h l r) = hstr ++ lstr ++ rstr
    where
        hstr = str ++ (show head) ++ "\n"
        lstr = makeTreeStr l
        rstr = makeTreeStr r
        makeTreeStr Empty = ""
        makeTreeStr tree = displayTree' (str ++ "*") tree ++ "\n"

Collectives™ on Stack Overflow

Displaying binary tree in Haskell

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related