Problem 71

The internal path length of a multiway tree is the total sum of the path lengths from the root to all nodes of the tree. The tree shown below has an internal path length of 9.

Write a function to determine the internal path length of a tree

mtree71 = Node 'a' [Node 'f' [Node 'g'], Node 'c'[], Node 'b'[Node 'd' [], Node 'e' []]]

internalPathLength mtree71 == 9

Unit Test

import Html
import List


type MTree a = MNode a (List (MTree a))


mtree70 = MNode 'a' 
          [ MNode 'f' [ MNode 'g' [] ]
          , MNode 'c' []
          , MNode 'b' [ MNode 'd' [], MNode 'e' [] ]
          ]


internalPathLength : MTree a -> Int
internalPathLength mtree =
    -- your implemenation goes here
    0


main =
    Html.text
        (if (test) then
            "Your implementation passed all tests."
         else
            "Your implementation failed at least one test."
        )


test : Bool
test =
    List.all ((==) True)
      [ internalPathLength (MNode 10 []) == 0
      , internalPathLength mtree70 == 9
      , internalPathLength test3 == 10
      , internalPathLength test4 == 4
      , internalPathLength test5 == 30
      ]     


test3 = MNode '1' [ MNode '2' [ MNode '3' [ MNode '4' [ MNode '5' [] ] ] ] ]
test4 = MNode 'a' [ MNode 'f' [], MNode 'g' [], MNode 'g' [], MNode 'g' [] ]
test5 = MNode '1' [ MNode '2' [ MNode '3' [ MNode '4' [ test4 ] ] ] ]

Solution

Solution