CODEWITHSUNDEEP
f#f#-interactivef#-datac#-to-f#f#-3.0
Oluwagbemi Kadri
Oluwagbemi Kadri

Reputation: 469

How to solve issue with insert function of f# trees

Please, I need some help with creating an insert function for a tree. The value in a given string list should be inserted to every branch and leaf in a tree. I have tried to solve this issue and have a very close answer but I am not able to write the function correctly to insert all the string values.

Code:

type Tree = Leaf of string | Branch of (string * Tree) list

let rec insertTree (lst : string list) (tree : Tree) : Tree =

        match lst, tree with
        | a::b::c::[], y  -> 
            match y with
            | Leaf(n) -> Branch[(a, Branch[(n, Leaf(c))])]
            | Branch[(x, p)] -> Branch[(x, Branch[(a, Branch[(b, insertTree (c::[]) p)])])]
            | _     -> insertTree (b::c::[]) y
        | _ , y    -> tree

Test: insertTree ["4"; "5";"6"] (Branch [("1", (Branch[("2", Leaf("3"))]))])

Gives: Branch [("1", Branch [("4", Branch [("5", Branch [("2", Leaf "3")])])])]

I want this instead: 

(Branch [("1", (Branch[("2", (Branch[("3",(Branch[("4",(Branch[("5", Leaf("6"))]))]))]))]))])

Upvotes: 0

Views: 64

Answers (1)

Ringil
Ringil

Reputation: 6537

I'm going to assume you just want to append the list in order to the final leaf and that all branches will have at most a single element in its list.

let insertTree (lst : string list) (tree : Tree) : Tree =
    let rec insertSingleIntotree x t = 
        match t with
        | Leaf(n) -> Branch[(n,Leaf x)]
        | Branch[(n,p)] -> Branch[(n, insertSingleIntotree x p)]
        | _ -> failwith "no idea what should happen here!"

    lst
    |> List.fold (fun acc x -> insertSingleIntotree x acc) tree

Upvotes: 1

Related Questions