Apologies for this weird question but I’m currently having some problem trying to explore all the nodes of a N-ary tree. Basically, I have the following tree:
Now, I want to explore all its nodes and print them out level by level which would basically give me an output of:
1 2 3 4 5 6 7 9 8 10 12 11
This would be printed in a single column, however, for better readability, I wrote it in as a row instead.
The code that I’ve written to attempt this is the following:
defmodule TreeTraversal do
defstruct data: nil, nodes: [], right: nil
def init(data), do: %TreeTraversal{data: data}
def get_nodes(left_node, right_node) do
case right_node do
nil -> right_node
_ ->
IO.inspect right_node.data
{left_node, right_node} =
right_node.nodes |> Enum.reduce({left_node, right_node}, fn child, {left_node, right_node} ->
case child do
nil -> {left_node, right_node}
_ -> if left_node, do: {%_MODULE_{left_node | right: child}, right_node}, else: {left_node, child}
end
end)
get_nodes(left_node, right_node.right)
end
end
def traversal(root) do
case root do
nil -> IO.puts "Completed Traversing"
_ ->
right_node = root
left_node = nil
root = get_nodes(left_node, right_node)
traversal(root)
end
end
end
However, this doesn’t really work properly as it only traverses the root and stops there which is extremely weird. Would really appreciate if someone offers their help. Been stuck on this for too long
I find it harder to do some of the common algorithms in Elixir, especially due to immutability; but I’ve been trying and getting better at it, so don’t be discouraged . If it can help, here’s an implementation of level order traversal for an N-Ary tree using Erlang’s :queue module to store nodes (which is based from this code in Python):
defmodule NAryTree
def level_order_traversal(node) do
queue = :queue.new()
queue = :queue.in(node, queue)
do_level_order_traversal(queue)
end
defp do_level_order_traversal({[], []}), do: nil
defp do_level_order_traversal(queue) do
queue =
Enum.reduce(1..:queue.len(queue), queue, fn _n, queue ->
{{:value, node}, queue} = :queue.out(queue)
IO.puts(node.val)
Enum.reduce(node.children, queue, fn child, queue ->
:queue.in(child, queue)
end)
end)
do_level_order_traversal(queue)
end
end
What I do not understand from your code is why do you have a left_node and a right_node. It seems to me that the right_node is different from the TreeTraversal struct because you call right_node.next but next isn’t an attribute of the TreeTraversal struct.
Yeah sorry about that. That was a typo. It should have been right_node.right. I am updating the right pointer of the children nodes using the left_node and using the right_node as the traversal pointer. I’ll edit my question above as well.
Thanks btw for your queue based implementation. I’ll take a look at it