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