# This is a function head. If a function with multiple clauses has default values,
# such as this one, a head must be provided. So BST.new() always uses an empty List `[]`
# for the elements argument if none is provided, and it uses this function `fn a, b -> a - b end`
# as the default sorting (comparator) function if none is provided.
def new(elements \\ [], comparator \\ fn a, b -> a - b end)

# This clause of the function matches if an empty List was used for the elements
# argument, or if no arguments were provided (because the defaults from the function
# head are used). It returns a %BST{} struct with the default `root` of nil and
# comparator function.
#
#    iex> BST.new()
#    %BST{comparator: #Function<3.51101074/2 in BST.new/1>, root: nil}
def new([], comparator), do: %__MODULE__{comparator: comparator}

# This clause matches when the elements arguments is a non-empty List. First,
# it calls `new([], comparator)` which is the version of this function defined
# directly above this one. After that, it 'loops' through each element in the
# list, calling `insert/2` to insert the element into the tree.
def new(elements, comparator) when is_list(elements) do
  tree = new([], comparator)

  Enum.reduce(elements, tree, fn element, tree ->
    insert(tree, element)
  end)
end

# This clause matches when only one item is passed as the element argument,
# insead of a List. It then calls the version of this function defined above,
# because using `new([element])` would now match the function definition
# that has the `is_list(elements)` guard.
def new(element, comparator), do: new([element], comparator)

I wrote the different versions of the new/2 function to make using the library
easier, but using them is not necessary.

For example doing this:

tree = BST.new(1)

Is effectively the same as this:

tree = BST.new()
tree = BST.insert(tree, 1)

Which is also the same result as this:

tree = BST.new([1])

The main problem that your library’s API has, is that it breaks parametricity, which is a fancy/formal way of saying that it is unintuitive to use because it treats certain kinds of input different than the others.

@siddhant3030 I have the feeling that your question might fall in the xyproblem category. It seems like you don’t really want a Binary Search Tree, but rather a way to delete duplicate elements from a list.
There are other ways to accomplish this, without ‘shoehorning’ the problem in a Binary Search Tree. If you actually want to work with duplicates and list elements in order you can:

• Sort a list and iterate over it from the front. This is the simplest solution. The only drawback is that it only works if you have the full list of elements available to you at the start.
• Use a Priority Queue to insert elements in as they come up. You can then pop the smallest element from this whenever you want.

A Priority Queue can be considered a ‘binary search tree with duplicates’.

Or you can just use map or ETS, both can work like such set.

You might find this useful.
It’s a complete implementation of Enumerable, Collectable and String.Chars for
a Set implemented using balanced binary trees:

Hey @siddhant3030, I wrote that BST library you linked. It was a side project that I was playing around with so I can’t guarantee the robustness of the code. But I am happy to answer any specific questions you have about it.