🎉 Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io 🎉
Avatar of n0mn0m

n0mn0m's solution

to Binary Search Tree in the F# Track

Published at Nov 06 2020 · 0 comments
Instructions
Test suite
Solution

Insert and search for numbers in a binary tree.

When we need to represent sorted data, an array does not make a good data structure.

Say we have the array [1, 3, 4, 5], and we add 2 to it so it becomes [1, 3, 4, 5, 2] now we must sort the entire array again! We can improve on this by realizing that we only need to make space for the new item [1, nil, 3, 4, 5], and then adding the item in the space we added. But this still requires us to shift many elements down by one.

Binary Search Trees, however, can operate on sorted data much more efficiently.

A binary search tree consists of a series of connected nodes. Each node contains a piece of data (e.g. the number 3), a variable named left, and a variable named right. The left and right variables point at nil, or other nodes. Since these other nodes in turn have other nodes beneath them, we say that the left and right variables are pointing at subtrees. All data in the left subtree is less than or equal to the current node's data, and all data in the right subtree is greater than the current node's data.

For example, if we had a node containing the data 4, and we added the data 2, our tree would look like this:

  4
 /
2

If we then added 6, it would look like this:

  4
 / \
2   6

If we then added 3, it would look like this

   4
 /   \
2     6
 \
  3

And if we then added 1, 5, and 7, it would look like this

      4
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Running the tests

To run the tests, run the command dotnet test from within the exercise directory.

Autoformatting the code

F# source code can be formatted with the Fantomas tool.

After installing it with dotnet tool restore, run dotnet fantomas . to format code within the current directory.

Further information

For more detailed information about the F# track, including how to get help if you're having trouble, please visit the exercism.io F# language page.

Source

Josh Cheek https://twitter.com/josh_cheek

BinarySearchTreeTests.fs

// This file was auto-generated based on version 1.0.0 of the canonical data.

module BinarySearchTreeTests

open FsUnit.Xunit
open Xunit

open BinarySearchTree

[<Fact>]
let ``Data is retained`` () =
    let treeData = create [4]
    treeData |> data |> should equal 4
    treeData |> left |> should equal None
    treeData |> right |> should equal None

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Smaller number at left node`` () =
    let treeData = create [4; 2]
    treeData |> data |> should equal 4
    treeData |> left |> Option.map data |> should equal (Some 2)
    treeData |> left |> Option.bind left |> should equal None
    treeData |> left |> Option.bind right |> should equal None
    treeData |> right |> should equal None

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Same number at left node`` () =
    let treeData = create [4; 4]
    treeData |> data |> should equal 4
    treeData |> left |> Option.map data |> should equal (Some 4)
    treeData |> left |> Option.bind left |> should equal None
    treeData |> left |> Option.bind right |> should equal None
    treeData |> right |> should equal None

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Greater number at right node`` () =
    let treeData = create [4; 5]
    treeData |> data |> should equal 4
    treeData |> left |> should equal None
    treeData |> right |> Option.map data |> should equal (Some 5)
    treeData |> right |> Option.bind left |> should equal None
    treeData |> right |> Option.bind right |> should equal None

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Can create complex tree`` () =
    let treeData = create [4; 2; 6; 1; 3; 5; 7]
    treeData |> data |> should equal 4
    treeData |> left |> Option.map data |> should equal (Some 2)
    treeData |> left |> Option.bind left |> Option.map data |> should equal (Some 1)
    treeData |> left |> Option.bind left |> Option.bind left |> should equal None
    treeData |> left |> Option.bind left |> Option.bind right |> should equal None
    treeData |> left |> Option.bind right |> Option.map data |> should equal (Some 3)
    treeData |> left |> Option.bind right |> Option.bind left |> should equal None
    treeData |> left |> Option.bind right |> Option.bind right |> should equal None
    treeData |> right |> Option.map data |> should equal (Some 6)
    treeData |> right |> Option.bind left |> Option.map data |> should equal (Some 5)
    treeData |> right |> Option.bind left |> Option.bind left |> should equal None
    treeData |> right |> Option.bind left |> Option.bind right |> should equal None
    treeData |> right |> Option.bind right |> Option.map data |> should equal (Some 7)
    treeData |> right |> Option.bind right |> Option.bind left |> should equal None
    treeData |> right |> Option.bind right |> Option.bind right |> should equal None

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Can sort single number`` () =
    let treeData = create [2]
    sortedData treeData |> should equal [2]

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Can sort if second number is smaller than first`` () =
    let treeData = create [2; 1]
    sortedData treeData |> should equal [1; 2]

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Can sort if second number is same as first`` () =
    let treeData = create [2; 2]
    sortedData treeData |> should equal [2; 2]

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Can sort if second number is greater than first`` () =
    let treeData = create [2; 3]
    sortedData treeData |> should equal [2; 3]

[<Fact(Skip = "Remove this Skip property to run this test")>]
let ``Can sort complex tree`` () =
    let treeData = create [2; 1; 3; 6; 7; 5]
    sortedData treeData |> should equal [1; 2; 3; 5; 6; 7]
module BinarySearchTree

type Node =
    { value: int
      left: Node option
      right: Node option }

let left node = node.left

let right node = node.right

let data node = node.value

let rec insert (tree: Node option) (value: int): Node =
    match tree with
    | None ->
        { value = value
          left = None
          right = None }
    | Some t when value > t.value -> { t with right = Some(insert t.right value) }
    | Some t -> { t with left = Some(insert t.left value) }

let create (items: int list): Node =
    items
    |> List.fold (fun acc item -> Some(insert acc item)) None
    |> Option.get

let rec sort (tree: Node option): int list =
    match tree with
    | None -> []
    | Some node -> (sort node.left) @ [ node.value ] @ (sort node.right)

let sortedData node =
    node
    |> Some
    |> sort

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?