The tree data structure that we will be traversing is as shown below:

You first need to represent the tree data structure. We will use a map:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  root = %{ data: "A", left: %{ data: "B", left: %{ data: "C", left: nil, right: nil }, right: %{ data: "D", left: nil, right: nil } }, right: %{ data: "E", left: nil, right: nil } } 

We are now ready to implement any of the tree traversal algorithms.

Will make use of Elixir’s pattern matching to accomodate what happens when their is an empty list, and what happens when the traversal gets to the leaves. That is why we have three different functions, which look kinda similar, but take different arguments.

## Pre Order Traversal

  1 2 3 4 5 6 7 8 9 10  #pre_order function, prints the root, the left then the right def pre_order(%{data: nil, left: nil, right: nil}) do [] end def pre_order(%{data: data, left: nil, right: nil}) do [data] end def pre_order(%{data: data, left: left, right: right}) do [data] ++ pre_order(left) ++ pre_order(right) end 

## In Order Traversal

  1 2 3 4 5 6 7 8 9 10  #in_order function, prints the left, the root then the right def in_order(%{data: nil, left: nil, right: nil}) do [] end def in_order(%{data: data, left: nil, right: nil}) do [data] end def in_order(%{data: data, left: left, right: right}) do in_order(left) ++ [data] ++ in_order(right) end 

## Post Order Traversal

  1 2 3 4 5 6 7 8 9 10  #post_order function, prints the left, the right then the root def post_order(%{data: nil, left: nil, right: nil}) do [] end def post_order(%{data: data, left: nil, right: nil}) do [data] end def post_order(%{data: data, left: left, right: right}) do post_order(left) ++ post_order(right) ++ [data] end 

## Calling the various functions

 1 2 3 4 5 6 7 8  result = Algos.pre_order(root) IO.puts(result) result2 = Algos.in_order(root) IO.puts(result2) result3 = Algos.post_order(root) IO.puts(result3) 

## The complete tree traversal algorithms code in Elixir

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71  defmodule Algos do #pre_order function, prints the root, the left then the right def pre_order(%{data: nil, left: nil, right: nil}) do [] end def pre_order(%{data: data, left: nil, right: nil}) do [data] end def pre_order(%{data: data, left: left, right: right}) do [data] ++ pre_order(left) ++ pre_order(right) end #in_order function, prints the left, the root then the right def in_order(%{data: nil, left: nil, right: nil}) do [] end def in_order(%{data: data, left: nil, right: nil}) do [data] end def in_order(%{data: data, left: left, right: right}) do in_order(left) ++ [data] ++ in_order(right) end #post_order function, prints the left, the right then the root def post_order(%{data: nil, left: nil, right: nil}) do [] end def post_order(%{data: data, left: nil, right: nil}) do [data] end def post_order(%{data: data, left: left, right: right}) do post_order(left) ++ post_order(right) ++ [data] end end defmodule Traverse do def print do root = %{ data: "A", left: %{ data: "B", left: %{ data: "C", left: nil, right: nil }, right: %{ data: "D", left: nil, right: nil } }, right: %{ data: "E", left: nil, right: nil } } result = Algos.pre_order(root) IO.puts(result) result2 = Algos.in_order(root) IO.puts(result2) result3 = Algos.post_order(root) IO.puts(result3) end end Traverse.print 

The output:

[Running] elixir "/Volumes/MAC/d/Algorithms/tree_traversal.exs"
ABCDE
CBDAE
CDBEA

[Done] exited with code=0 in 3.37 seconds


Thank you for reading. Feel free to contact me if you have any question, comment or suggestion. 🎉