# How to implement a Binary Search Tree using Elixir?

I want to implement a BST using elixir can someone help me with how to approach this ?

Basically, nested improper lists. `[right|left]` nodes until you get to a branch that has a value instead of another node.

Either what @sribe suggested or you can use 2-ary tuples which will provide equivalent feature set. So you will have tuple in form of `tree :: {tree() | node(), tree() | node()}`.

I found this

But here the problem is Iâ€™m not able to understand how these things are working

`````` def new(elements \\ [], comparator \\ fn a, b -> a - b end)

def new([], comparator), do: %__MODULE__{comparator: comparator}

def new(elements, comparator) when is_list(elements) do
tree = new([], comparator)

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

def new(element, comparator), do: new([element], comparator)
``````

What do you have problems with? Understanding the algorithm behind Binary Search Trees, or reading the mentioned Elixir code?

I think you need 2 things:

1. How to implement a tree structure in Elixir
2. How to implement the algorithms to transform list to BST and how to traverse it.

Binary Search I know. I have implemented using javascript. This elixir code iâ€™m not able to understand

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.

Hey thanks for replying. Basically I didnâ€™t understand this part.

Here youâ€™re taking new function which takes list of elements and what does comparator do here?

Can you explain these four function and how does it work?

``````def new(elements \\ [], comparator \\ fn a, b -> a - b end)

def new([], comparator), do: %__MODULE__{comparator: comparator}

def new(elements, comparator) when is_list(elements) do
tree = new([], comparator)

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

def new(element, comparator), do: new([element], comparator)
``````
``````# 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])
``````
6 Likes

The comparator is a function that is stored in the BST struct, and is used each time a new element is inserted or updated so the library knows how to sort the elements correctly. For example, using the default comparator `fn a, b -> a - b end` would correctly sort integers, but a different comparator would need to be used if you are sorting a list of User structs like `%User{name: "Alice"}` that you want to organize by name.

This reads quite pythonicâ€¦ As convinient as this actually seems, at the end it will only cause confusionâ€¦

Also it causes inconsistencies.

What if I want a BST with the single element `[1, 2, 3, 4]`? I have to wrap it in an extra list, but if I want a singleton BST of a number, an atom, or even a pid, just the value is enoughâ€¦ Even a set, which is a collection similar to how lists are, will be treated like singleton values hereâ€¦

That is an interesting use case. I would have to see an example of this data set to contemplate the right approach. You could wrap your list in another list like you mentionedâ€“my first instinct would be to put those values in a map.

What about in the case of list of integers? Will it return the sorted list

Also what happens if I put two similar items in a list?

Like this

[1, 4, 3, 7, 4]

A binary search tree by definition has distinct keys, so duplicates are not allowed. This library would â€śreplaceâ€ť the duplicate key. So if you create a tree with those values, the data structure looks like this (note 4 only ends up appearing once)

``````iex> tree = BST.new([1, 4, 3, 7, 4])
%BST{
comparator: #Function<3.51101074/2 in BST.new/1>,
root: %BST.Node{
data: 1,
left: nil,
right: %BST.Node{
data: 4,
left: %BST.Node{data: 3, left: nil, right: nil},
right: %BST.Node{data: 7, left: nil, right: nil}
}
}
}
``````

You can then use the `to_list/1` function to get the sorted list

``````iex> BST.to_list(tree)
[1, 3, 4, 7]
``````

So what if I want to create a duplicate keys. In that case how do I do it?

Why do you want to do that?

A BST is an optimised data structure to answer the question â€śhas a given element been in the original inputâ€ť, not the question about how often it was in thereâ€¦

Itâ€™s just a thought. I want to make that mistake where I can put duplicate keys and if I can write a function where I can delete all those duplicate keys. So basically something like this

Input
[1, 4, 7, 3, 4, 5, 4]

Output
[1, 7, 3, 5]

Sorry, I do not get itâ€¦