F# Binary Tree and Tree Traversal

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.