I am still trying to figure how to use the return value and need help with that. Perhaps also the algorithms are incorrect
elevatika
NobbZ
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
elevatika
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.
0
NobbZ
elevatika
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
0
NobbZ
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.
0
elevatika
data: "C",
left: %{
data: nil,
left: nil,
right: nil
},
right: %{
data: nil,
left: nil,
right: nil
}
you mean like this?
0
NobbZ
elevatika
. I’m still learning
NobbZ
A common approach is to use either an atom that represents the empty tree, eg. nil or :empty, or to just use a empty map (%{}).
2