The tree data structure that we will be traversing is as shown below: A Tree Data Structure

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. 🎉

comments powered by Disqus

You might also like