Tree Traversal With Elixir
Tags: elixir, trees
Published: 2020-01-05 21:01:51

This is a simple implementation of depth-first and breadth-first traverse algorithms in Elixir.

First, let's talk about [Elixir](https://en.wikipedia.org/wiki/Elixir_(programming_language)): Elixir is a functional, dynamically-typed, general purpose programming language design for concurrency. It's based on the Erlang programming language and runs on its virtual machine (BEAM).

And tree traversal algorithms:

**Trees** are a recursive data structured that should be in every programmer's arsenal. A tree can be either leaf node or a node that contains one or more subtrees. Nodes can carry data, typically a node value and a node key.
Trees differ from list in that list are linear structures and trees have a branching structure. Each element in a list points to the rest of list (a linked-list). Whereas each element in a tree points to one or more subtrees.
Trees are a kind of graph and they come in different kinds depending of the branching structure and node contents; unary, binary, binary search and N-ary trees are some examples.

**Traversing** a tree means to apply some operation on its nodes in a well-defined order.

**Depth-first traverse** algorithm consists of for each node, visit first the node itself, then start visiting from the leftmost subtree until you reach the rightmost subtree. Repeat this for each subtree until all nodes have been visited.
The algorithm uses a [stack](https://www.geeksforgeeks.org/stack-data-structure/) -- implicitly or explicitly -- to store the nodes that need to be visited.

**Breadth-first traverse** algorithm consists of visiting each node at depth 0, then each node at depth 1, then depth 3, and so forth until all nodes have been visited.
This algorithm uses a [queue](https://www.geeksforgeeks.org/queue-data-structure/) -- implicitly or explicitly -- instead of a stack to store the nodes before visit them.

## Let's get to the code.

First let's create a *elixir_trees* project:

`mix new elixir_trees`

And define our tree data estructure in `elixir_trees/lib/tree.ex` like this:

![Tree data-type](https://thepracticaldev.s3.amazonaws.com/i/o41frm8k20uvnv1vjvvw.png)

A tree is struct with the fields: value(the data to perform operations with), key (an optional unique id for the node) and children (the subtrees). Also we add the type spec to improve consistency and readability.

Next we define the tree traversal module in `elixir_trees/lib/tree_traversal.ex` and define the types for the function specs and aliases for the tree datatype:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/h3aulwkzxcchw3sijmtm.png)

Now we write our functions, let's start with depth-first:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/ras6697jjhfxt5xpufe0.png)

Lines 54-56 declare and add the *typespec* to the function. **dfs** receives 3 arguments: a stack to store the nodes, a function operation that will be apply when visiting each node and history which is a list with accumulated result of applying the function operation while traversing the tree. 
As specify at lines 11-12, the operation function receives 3 arguments, the node value, the node key and the accumulated history, and returns a tuple with the result of the operation and a atom telling the algorithm wether to continue traversing or to stop.
Let's take a look at some simple valid operation functions to pass to the algorithm:

``` 
fn (x, _, _) when x < 0 -> {:stop, x}
   (x, _, _) -> {:continue, x} 
end
```

``` 
fn (x, _, []) -> {:continue, x}
   (x, _, h) -> {:continue, x + hd(h)} 
end
```

The first one checks wether negative values exists in the tree and stop as soon as it finds one, it continues otherwise. And the second one sums all the values of the nodes in the tree.

Now, line 58 deals with base case when the stack is empty and returns the traverse history as a result, the stack is implemented a regular list. The result of visiting each node is arrange from last to first i.e the result of visiting the root of the tree is the last element in the history.
Line 60 deals with the case where the stack is non-empty and uses patter-matching to get the tree node properties and we pass that to the `next/7` function along with `dfs/3` function to apply and indirect recursive call and continue process.

`next/7` is defined as:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/oee9a9zo27ddzphb0tf4.png)

The function applies and checks the result of applying the function operation to the node, deciding whether to stop or continue traversing. If the operation result tells it to stop it simply add the result value to the existing history and terminates, if not, it uses the `tree_insert/2` function to scheduled the next nodes to be visit (we'll explaning this one later) and pipes down the result to the caller function, in this case `dfs/3`. 

And that's all for the dfs function now, let's implement the breadth-first search one:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/yt3kmzhzq4au3p1tly8c.png)

This is pretty much the same as `dfs/3`. The only differences are the the base case at line 71 that doesn't check for an empty stack anymore, it checks for an empty queue, same for lines 74-77, instead of popping a stack we pop a queue. The queue we are using is the [amortized queue](https://en.wikipedia.org/wiki/Amortized_analysis) [implementation in Erlang](http://erlang.org/doc/man/queue.html). After that we do the same as before, we pass along node fields, queue and function to `next/7`.

Now that we've seen the implementation of dfs and bfs algorithms let's explain the missing helper functions `tree_insert/2` and `apply_operation/4`:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/ynrxq09b0rzgsh289u5l.png)

`tree_insert/2` deals with pushing/popping nodes to the queue/stack.

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/yg1u5u2ouj360rdrsslc.png)

`apply_operation/4` checks the arity of the operation function and raises an exception if it's not 3, otherwise it applies the function to the arguments and returns the result.

Finally all that's missing is main function to wrap it all up:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/pb7z3orh4hqegxyrwc70.png)

Traverse receives the tree, the operation function and an atom with the name of the algorithm we wish to use.
And The initial stack and queue are initialized by this pair:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/gtyrkkkovljsmftle3e4.png)

You can find the full source code [here](https://github.com/crisefd/elixir_trees/tree/master/lib)