Tree traversal in elixir, pre-order, in-order, post-order What am I doing wrong?

Questions / Help
,
1

I am learning Elixir and wanted to try implementing simple tree traversal algorithms. However, I am not getting the desired results. What am I doing wrong?

defmodule Algos do
    #pre_order function, prints the root, the left then the right
    def pre_order(node, nodes) do
        next = [nodes | node.data]
        if (node && node.left) do
            Algos.pre_order(node.left, next) 
        end
        if (node && node.right) do
            Algos.pre_order(node.right, next)
        end
        next
    end

    #in_order function, prints the left, the root then the right
    def in_order(node, nodes) do
        if (node && node.left) do 
            Algos.in_order(node.left, nodes) 
        end
        next = [nodes | node.data]
        if (node && node.right) do
            Algos.in_order(node.right, next)
        end
        next
    end

    #post_order function, prints the left, the right then the root
    def post_order(node, nodes) do
        if (node && node.left) do
            Algos.post_order(node.left, nodes)
        end
        if (node && node.right) do
            Algos.post_order(node.right, nodes)
        end
        [nodes | node.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 looks as follows

[Running] elixir "/Volumes/MAC/d/Algorithms/tree_traversal.exs"
A
A
A

[Done] exited with code=0 in 3.891 seconds
2

Hello and welcome,

I did not read all the code, but this is not working as You expect, it should be an element first, then a list. If needed, You can reverse the list at the end.

[node.data | nodes]

Remember a list is [head | tail], with head being an element pushed at the head, while tails is a list.

1 Like
3

What output would you expect instead?

You don’t use the return values of th recursive calls, they won’t have any effect besides heating your room.

2 Likes
4

Hi. Thanks.

I have edited the section of the code that way but still not working.

5

What does “not working” mean? Do you get an error, if yes which? Is the output different from what you expect, if yes how?

And how does your current code look like?

6

I expect the function to return a list after completing the traversal

7 
defmodule Algos do
    #pre_order function, prints the root, the left then the right
    def pre_order(node, nodes) do
        next = [node.data | nodes]
        if (node && node.left) do
            Algos.pre_order(node.left, next) 
        end
        if (node && node.right) do
            Algos.pre_order(node.right, next)
        end
        next
    end

    #in_order function, prints the left, the root then the right
    def in_order(node, nodes) do
        if (node && node.left) do 
            Algos.in_order(node.left, nodes) 
        end
        next = [node.data | nodes]
        if (node && node.right) do
            Algos.in_order(node.right, next)
        end
        next
    end

    #post_order function, prints the left, the right then the root
    def post_order(node, nodes) do
        if (node && node.left) do
            Algos.post_order(node.left, nodes)
        end
        if (node && node.right) do
            Algos.post_order(node.right, nodes)
        end
        [node.data | nodes]
    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

That is the current code.

I still get only the first node “A” returned by each function.

[Running] elixir "/Volumes/MAC/d/Algorithms/tree_traversal.exs"
A
A
A

[Done] exited with code=0 in 3.304 seconds

I expect the functions to traverse the tree, create a list, and then return that list

8

You are not using the return values of the recursive calls. They do not have an effect.

9

What would be the best way to return the list after completing the recursive calls?
…

I’m still struggling to understand Elixir

10

You already return it. Though you are not using the returned list.

1 Like
11

Have you been able to make any progress?

You “liked” my previous post, so I can assume you read it. If you have any problems understanding the hints, please feel free to ask more questions.

12

I am still trying to figure how to use the return value and need help with that. Perhaps also the algorithms are incorrect

13

Well you call a function f, it returns a value. Currently you do not assign that value. You can assign it by using =:

list = pre_order(node.left, next)

As far as I remember, “preorder” is basically [data] ++ pre_order(left) ++ pre_order(right), therefore this is where I would start.

def pre_order(%{data: data, left: left, right: right}) do: [data] ++ pre_order(left) ++ pre_order(right)

This provides you the generic case of the pattern match, you now need to provide the base case which breaks the recursive call. This version will crash on the leafs.

4 Likes
14

Using your answer, I modified the code as follows:

defmodule Algos do
    #pre_order function, prints the root, the left then the right
    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: data, left: nil, right: nil}) do
        [data]
    end
    def in_order(%{data: data, left: left, right: right}) do
         pre_order(left) ++ [data] ++ pre_order(right)
    end
    
    #post_order function, prints the left, the right then the root
    def post_order(%{data: data, left: nil, right: nil}) do
        [data]
    end
    def post_order(%{data: data, left: left, right: right}) do
         pre_order(left) ++ pre_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 code worked as expected:

[Running] elixir "/Volumes/MAC/d/Algorithms/tree_traversal.exs"
ABCDE
BCDAE
BCDEA

[Done] exited with code=0 in 2.978 seconds

Thank you so much.

15

Are you sure, this is the base case? How would you travers an empty tree?

16

Is there a shorter way other than duplicating the function this way?

#pre_order function, prints the root, the left then the right
#for empty
    def pre_order(%{data: nil, left: nil, right: nil}) do
        []
    end
#for leafs
    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
17

You should reconsider how you represent an empty tree…

Tip: usually leafs are represented by having left and right pointing to a/the empty tree.

18 
                    data: "C", 
                    left: %{
                        data: nil,
                        left: nil,
                        right: nil
                    },
                    right: %{
                        data: nil,
                        left: nil,
                        right: nil
                    }

you mean like this?

19

Not really, how would you represent a node value of nil then?

1 Like
20

I thought the representation I used is correct :slight_smile:. I’m still learning