How do I check the complexity?

So I have a binary tree that I have created using a map. I want to know the worst and average time of complexity?

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

# iex(1)> tree = BST.new(100)
# %{left: :leaf, right: :leaf, value: 100}
# iex(2)> tree1 = BST.insert(tree, 200)
# %{left: :leaf, right: %{left: :leaf, right: :leaf, value: 200}, value: 100}
# iex(3)> tree2 = BST.insert(tree, 50)
# %{left: %{left: :leaf, right: :leaf, value: 50}, right: :leaf, value: 100}
# iex(4)> tree2 = BST.insert(tree1, 50)
# %{
#   left: %{left: :leaf, right: :leaf, value: 50},
#   right: %{left: :leaf, right: :leaf, value: 200},
#   value: 100
# }

  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

How do I calculate this?

Your insert might produce duplicate values in the BST, as it considers the new item as “bigger” if it is not smaller, meaning “equal” items are not equal, but the new item is “bigger” than the old.

Also, as your tree is not self balancing, insertion is O(n), as in a worst case scenario (input is a pre-sorted list) all insertions will happen rightmost.

1 Like

And what if I want to delete the node?

What do I know? You haven’t shown the function. Though as in worst case your tree will be just like a linked list, it has the linked lists runtime and memory complexity of a linked list as well, assuming you have not done something completely borked in your implementation, but it can’t be better than a linked list.

Here it is

def delete_node(tree, node_value) do
    if exists?(tree, node_value) do
      delete tree, node_value
    else
      nil
    end
  end

  defp delete(tree, node_value) do
    cond do
    tree.value == node_value -> del(tree)
    tree.value <  node_value ->
    %{left: tree.left,
      value: tree.value,
      right: delete(tree.right, node_value)}
      tree.value > node_value ->
        %{left: delete(tree.left,node_value),
          value: tree.value,
          right: tree.right}
    end
  end

  defp del(%{left: :leaf,  value: _, right: right}), do: right
  defp del(%{left: left, value: _, right: :leaf}),   do: left
  defp del(%{left: left, value: _, right: right}) do
    %{left: left, value: min(right), right: delete(right, min(right))}
  end

  defp min(%{left: :leaf,  value: val, right: _}), do: val
  defp min(%{left: left, value: _,   right: _}), do: min left


  def exists?(tree, node_value) do
    e tree, node_value
  end

  defp e(:leaf, _), do: false
  defp e(%{value: node_value, left: _, right: _}, node_value), do: true
  defp e(tree_node, node_value) do
    if node_value < tree_node.value do
      e tree_node.left, node_value
    else
      e tree_node.right, node_value
    end
  end

But here the problem is. I’m deleting the duplicate values one by one and I want to delete all the duplicate values at once. Can we do that?

As I said already in the other thread and here in my first reply, you need to take care for all cases, :lt, :gt and :eg.

Stop treating :eq the same as :gt, thats not true! That does not properly work!

This was a interview question. They don’t want to handle all the cases. I need to store those values and delete it at once all the duplicate values.

Do it during insert, thats how properly implemented BSTs deal with it, regardless of the fact if they are balanced or not.

Deleting them after the fact, does require you to walk a lot of the tree, deleting offending nodes from the deepest (to the deepest is possible as well, but might cause a lot more reorganizing than necessary)…

I don’t really understand why it would make much sense to do that. However if you really do need to do that then it might make sense to add another key on each node that holds all the duplicates of that value. At least that way your BST structure still makes sense as a BST and still has the characteristics of a BST. As @NobbZ is saying, if you don’t handle the equal case the whole thing breaks.