levelOrderTraversal.tri (1912B)
1 !import "prelude" !Local 2 3 main = exampleTwo 4 -- Level Order Traversal of a labelled binary tree 5 -- Objective: Print each "level" of the tree on a separate line 6 -- 7 -- We model labelled binary trees as nested lists where values act as labels. We 8 -- require explicit notation of empty nodes. Empty nodes can be represented 9 -- with an empty list, `[]`, which evaluates to a single node `t`. 10 -- 11 -- Example tree inputs: 12 -- [("1") [("2") [("4") t t] t] [("3") [("5") t t] [("6") t t]]]] 13 -- Graph: 14 -- 1 15 -- / \ 16 -- 2 3 17 -- / / \ 18 -- 4 5 6 19 20 label = node : head node 21 22 left = node : (if (emptyList? node) 23 [] 24 (if (emptyList? (tail node)) 25 [] 26 (head (tail node)))) 27 28 right = node : (if (emptyList? node) 29 [] 30 (if (emptyList? (tail node)) 31 [] 32 (if (emptyList? (tail (tail node))) 33 [] 34 (head (tail (tail node)))))) 35 36 processLevel = y (self queue : if (emptyList? queue) 37 [] 38 (pair (map label queue) (self (filter 39 (node : not? (emptyList? node)) 40 (append (map left queue) (map right queue)))))) 41 42 levelOrderTraversal_ = a : processLevel (t a t) 43 44 toLineString = y (self levels : if (emptyList? levels) 45 "" 46 (append 47 (append (map (x : append x " ") (head levels)) "") 48 (if (emptyList? (tail levels)) "" (append (t (t 10 t) t) (self (tail levels)))))) 49 50 levelOrderToString = s : toLineString (levelOrderTraversal_ s) 51 52 flatten = foldl (acc x : append acc x) "" 53 54 levelOrderTraversal = s : append (t 10 t) (flatten (levelOrderToString s)) 55 56 exampleOne = levelOrderTraversal [("1") 57 [("2") [("4") t t] t] 58 [("3") [("5") t t] [("6") t t]]] 59 60 exampleTwo = levelOrderTraversal [("1") 61 [("2") [("4") [("8") t t] [("9") t t]] 62 [("6") [("10") t t] [("12") t t]]] 63 [("3") [("5") [("11") t t] t] [("7") t t]]]