How to implement a Binary Search Tree using Elixir?

Questions / Help
21

So, after reading in the BST, just delete the node with the value 4…

22

This is what I’m trying to implement.

defmodule Bst do

  def new(value) do
    %{value: value, left: :leaf, right: :leaf}
  end

  def insert(:leaf, node_value), do: new node_value

  def insert(%{value: value, left: left, right: right}, node_value) do
    if node_value < value do
      %{value: value, left: insert(left, node_value), right: right}
    else
      %{value: value, left: left, right: insert(right, node_value)}
    end
  end

end

In this what’s happening when we give the duplicate value it will store it.

Like this

iex(1)> tree = Bst.new(1)
%{left: :leaf, right: :leaf, value: 1}
iex(2)> Bst.insert(tree, 10)
%{left: :leaf, right: %{left: :leaf, right: :leaf, value: 10}, value: 1}
iex(3)> tree1 = Bst.insert(tree, 10)
%{left: :leaf, right: %{left: :leaf, right: :leaf, value: 10}, value: 1}
iex(4)> tree2 = Bst.insert(tree1, 6) 
%{
  left: :leaf,
  right: %{
    left: %{left: :leaf, right: :leaf, value: 6},
    right: :leaf,
    value: 10
  },
  value: 1
}
iex(5)> tree3 = Bst.insert(tree2, 0)
%{
  left: %{left: :leaf, right: :leaf, value: 0},
  right: %{
    left: %{left: :leaf, right: :leaf, value: 6},
    right: :leaf,
    value: 10
  },
  value: 1
}
iex(6)> tree4 = Bst.insert(tree3, 10)
%{
  left: %{left: :leaf, right: :leaf, value: 0},
  right: %{
    left: %{left: :leaf, right: :leaf, value: 6},
    right: %{left: :leaf, right: :leaf, value: 10},
    value: 10
  },
  value: 1
}

But thankyou you helped a lot. Let me know if we can improve this

23

You are treating equal values the same way as you treat greater values.

On insertion you need to handle less than (left), greater than (right) and equal (here).

1 Like
24

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’.

4 Likes
25

Hi Thanks for your time. I’m just playing with binary search tree. I have a clear idea about what I’m implementing. Maybe I wasn’t clear before but sorry for that.

26

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

2 Likes
27

Yes, those would be examples of concrete datatypes that implement the abstract datatype known as ‘a priority queue’.

@siddhant3030 No worries! Unfortunately I still have a bit of trouble understanding what you want to implementing :blush:. In any case, wanting to try something yourself is always a good reason to tinker with stuff :wink: .

1 Like
28

Thanks for taking a look and teaching me a new word :sweat_smile:

I agree that it would be more intuitive to treat inputs consistently. I’m updating the api to always expect a list instead of the single element option https://github.com/bnhansn/bst/commit/5bb5e3ccff81266c279d081f5a5eabbebe3425d7. This allows the new/2 function to only have one clause and hopefully makes the code easier to read.

1 Like
29

This might be a useful starting point Rosetta Code example of BST in Elixir

1 Like
30

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

2 Likes