Tree traversal with elixir

Hello everyone! I found some algorithms for depth-first search and breadth-first search in elixir. The author’s nickname is sashaafm.
But I can’t understand the format in which trees take these algorithms as input and how they work. Maybe you can help me figure this out?

  @doc """
  Performs a Breadth-First Search in the given 'tree'. The nodes' values are
  returned as a list.
  """
  @spec breadth_first_search(%{}) :: list(any)

  def breadth_first_search(tree) do
    bfs(tree)
  end

  defp bfs(%{value: val, left: :leaf, right: :leaf}) do
    [val]
  end

  defp bfs(%{value: val, left: :leaf, right: right}) do
    [val] ++ bfs(right)
  end

  defp bfs(%{value: val, left: left, right: :leaf}) do
    [val] ++ bfs(left)
  end

  
  defp bfs(%{value: val, left: left, right: right}) do
    [val] ++ bfs(left) ++ bfs(right)
  end

  def main do
  end

  @doc """
  Does a Depth-First Search in the given 'tree'. The nodes' values are returned in a list. The order of the search is passed into 'order' using
  the atoms ':in_order', ':pre_order' or ':post_order'
  """
  @spec depth_first_search(%{}, atom) :: list(any)

  def depth_first_search(tree, order)
      when order == :pre_order or
             order == :in_order or
             order == :post_order do
    dfs(tree, order)
  end

  defp dfs(:leaf, _), do: []
  defp dfs(%{value: val, left: :leaf, right: :leaf}, _), do: [val]

  defp dfs(tree_node, order) do
    case order do
      :pre_order ->
        [tree_node.value] ++ dfs(tree_node.left, order) ++ dfs(tree_node.right, order)

      :in_order ->
        dfs(tree_node.left, order) ++ [tree_node.value] ++ dfs(tree_node.right, order)

      :post_order ->
        dfs(tree_node.left, order) ++ dfs(tree_node.right, order) ++ [tree_node.value]
    end
  end

I hope my question satisfies the forum rules, thanks in advance!

My guess would be a tree composed of nodes like so:

@type tree_node :: %{value: term(), left: tree_node() | :leaf, right: tree_node() | :leaf}

Im newbie to this, so how can i pass, for instance, this current tree? I 1 is root, it will be the first argument in this map?

The tree in this image wont fit in the code above, as the root node (1) doesn’t just have a left (2) and right (8), but also a the (7) node. What are you trying to accomplish?

I’m understood, thank you. apparently this is not the code that I need. I want to dfs and bfs functions, which takes tree, start node and end node and returned path from start to end.

A real tree structure may not be the best to manipulate in a functional language. Everything is immutable so if you add one node deep, everything above it must change. An alternative is to use an approach like database tables. If you have a unique id for each node, just put everything in a map. Then, you have a separate map for the parent to children relationship based on the keys.

2 Likes

The gb_trees library in the Erlang stdlib might do what you want:

https://erlang.org/doc/man/gb_trees.html

or if paths are really important, maybe you have a digraph instead of a tree:

https://erlang.org/doc/man/digraph.html

3 Likes

Oh thank you. The problem is that I need an algorithm in a pure language without libraries, but now I understand that the elixir is not the best choice for this, and maybe Erlang isn’t best too. I will think about OOP languages, but that not interesting for me at all

Traversing a tree in a functonal programming language like Elixir/Erlang is doable, but I’m not sure what kind of tree do you expect. Maybe you could show us an example from IEx?

Are you trying to implement DFS/BFS? On what kind of tree? A binary tree (where each node has at most two children) or a ternary tree (where each node has at most three children)?

Both of the linked modules are part of the Erlang standard library - they are packaged with the interpreter, the same way modules like Enum or File are.

If your goal is to learn about the implementation of BFS and DFS, the source code of those modules should provide you with good examples of recursion patterns, the same way this repo provided the code in your original post.

What? For me it is the easiest to do in FP. Of course, you need to replace whole branch up to root to change one leave, but other than that you always keep the rest intact. FP are made for traversing and manipulating such structures.

See that a lot of tree or tree-like structures work like that:

  • Git (DAG)
  • BitTorrent (Merkle Tree)
  • HAMT

All of that is just made out of immutable nodes, and on each change you need to replace whole path, but it is quite easy and simple to implement in FP.

6 Likes

The hard bit is getting information about the surrounding or distant nodes. In a classic depth-first traversal you only have the current node(and its children) available, but not the siblings or parent. It’s also hard to change a non-child node.
However there are techniques to make it easy, like zippers. Clojure zippers made it click for me: Clojure Zippers

1 Like