Tree Traversal With Elixir

Cristhian Fuertes — Sun, 05 Jan 2020 21:01:51 +0000

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

First, let's talk about Elixir: 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 -- 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 -- 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:

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:

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

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:

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:

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 implementation in Erlang. 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:

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

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:

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:

You can find the full source code here

DEV Community: Cristhian Fuertes

Tree Traversal With Elixir

Let's get to the code.