F# Binary Tree and Tree Traversal

Question

So for an side exercise on exercism I implemented a BinarySearchTree. I was confident in implementing the creation of the binary tree. But I'm very unsure about the traversal of the tree. So I came up with two implementations of the traversal algorithm - which one is the "better" solution?

I'm learning about F# because I want to learn Functional Programming. This is code review - so any criticism is welcome!

module BinarySearchTree 

type Node<'a> =
    { Left: Node<'a> option
      Right: Node<'a> option
      Data: 'a }

let left (node: Node<'a>)  = node.Left

let right (node: Node<'a>) = node.Right

let data (node: Node<'a>) : 'a = node.Data

let rec insertNode (root: Node<'a> option) (nextValue: 'a) : Node<'a> =
    match root with
    | Some root -> if nextValue <= root.Data then { root with Left = Some(insertNode root.Left nextValue) }
                   elif nextValue > root.Data then { root with Right = Some(insertNode root.Right nextValue) }
                   else root
    | None -> { Left=None; Right=None; Data=nextValue }

let create (items: 'a list) : Node<'a> =
     items
     |> List.fold (fun (acc: Option<Node<'a>>) (item: 'a) -> Some(insertNode acc item)) None
     |> function
        | None -> failwith "Failed to construct binary tree. You must pass a valid item list."
        | Some root -> root  

let sortedData (node: Node<'a>) : ('a list) =
    let rec traverse (acc: 'a list) (node: Node<'a>)  =     
        match (node.Left, node.Right) with
        | Some left, Some right -> seq {
                                   yield! node.Data::acc
                                   yield! (traverse [] left)
                                   yield! (traverse [] right)}
                                   |> Seq.toList
        | Some left, None -> traverse (node.Data::acc) left
        | None, Some right -> traverse (node.Data::acc) right
        | None, None -> node.Data::acc

    List.sort (traverse [] node)

And the alternative implementation of sortedData:

let sortedData (node: Node) : (int list) =



 let rec traverse (acc: int list) (node: Node)  =     
        match (node.Left, node.Right) with
        | Some left, Some right -> (node.Data::acc)@(traverse [] left)@(traverse [] right) 
        | Some left, None -> traverse (node.Data::acc) left
        | None, Some right -> traverse (node.Data::acc) right
        | None, None -> node.Data::acc

    List.sort (traverse [] node)

Answer 1

In general in F# we try to minimize the use of explicit type declaration on function arguments:

let left (node: Node<'a>) = node.Left

becomes

let left node = node.Left

etc.

---

The function insertNode violates the single responsibility principle in that if root = None then it creates a new tree/root node instead of actual inserting the value.

Personal I wouldn't allow root to be Option/None

Instead I would provide a function called newTree taking a 'a value as argument and returning a Node<'a>

---

let rec insertNode (root: Node<'a> option) (nextValue: 'a) : Node<'a> = ...

In general you should have object in question of the module as the last argument of a function in order to make use of the pipe operator:

let rec insertNode value root =...

root |> BinarySearchTree.insertNode value

---

sortedData seems overly complicated - maybe from the use of List.sort. In principle it's just a depth-first-search (dfs), where you for each node can concatenate the values in the left child node with the value of the node itself concatenated with the values in the right child node:

For a list it could be:

let toList root =
    let rec dfs optNode =
        match optNode with
        | Some node -> (dfs (left node))@(data node::dfs (right node))
        | None -> []

    dfs (Some root)

Or if you prefer a Sequence (which I do):

let toSeq root =
    let rec dfs optNode =
        match optNode with
        | Some node -> seq {
            yield! dfs (left node)
            yield data node
            yield! dfs (right node)
            }
        | None -> Seq.empty

    dfs (Some root)

I call the functions toList and toSeq. Maybe toOrderedList/Seq are better names.

---

You could consider to extend the List-module with a toBinaryTree items instead of the create items function. That way it is possible to write:

let data = [ 5; 8; 1; 5; 1; 2; 2; 4; 6; 3 ]
let root = data |> List.toBinaryTree

which may be more intuitive

---

In the create items function you should consider to sort the items and do a binary insertion in order to create a balanced tree, because if you provide a list of items that is sorted then your function will merely produce a singly linked list of nodes using only one of the child nodes instead of a tree.

You should consider to provide a function that can balance an existing tree.

---

As an alternative to the Node<'a> type as a record type, you could consider to define it as a discriminated union type with the following definition:

type Node<'a> =
    | Empty
    | Node of Data:'a * Left:Node<'a> * Right:Node<'a>

That is more in line with the functional style of F# and your functions become somewhat more simple and intuitive:

module BinaryTree =

let data = function Empty -> failwith "Empty Tree" | Node (d, _, _) -> d
let left = function Empty -> Empty | Node (_, l, _) -> l
let right = function Empty -> Empty | Node (_, _, r) -> r

let first root = 
    let rec goLeft node =
        match node with
        | Empty -> None
        | Node (d, ln, _) ->
            match ln with
            | Empty -> Some d
            | Node _ -> goLeft ln

    goLeft root

let last root = 
    let rec goRight node =
        match node with
        | Empty -> None
        | Node (d, _, rn) ->
            match rn with
            | Empty -> Some d
            | Node _ -> goRight rn

    goRight root

let rec insert data root =
    match root with
    | Empty -> Node(data, Empty, Empty)
    | Node (d, l, r) ->
        match data <= d with
        | true -> Node (d, l |> insert data, r)
        | false -> Node (d, l, r |> insert data)

let toOrderedSeq root =
    let rec dfs node =
        match node with
        | Empty -> Seq.empty
        | Node (d, ln, rn) -> seq {
                yield! dfs ln
                yield d
                yield! dfs rn
            }

    dfs root


module List =
    let toBinaryTree data = data |> List.fold (fun n x -> n |> BinaryTree.insert x) Empty

As seen, the use of option is unnecessary and the insert function is consistent, because an Empty node as root is also a Node<'a>/Tree - just without any elements.