# Level Order Traversal of N-ary Tree

Hey! Hope everyone is having a great day.

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
``````

For the given tree (your tree):

``````    %__MODULE__{
val: 1,
children: [
%__MODULE__{
val: 2,
children: [
%__MODULE__{
val: 5
}
]
},
%__MODULE__{
val: 3,
children: [
%__MODULE__{
val: 6,
children: [
%__MODULE__{
val: 9
},
%__MODULE__{
val: 8
},
%__MODULE__{
val: 10,
children: [
%__MODULE__{
val: 11
}
]
}
]
},
%__MODULE__{
val: 7,
children: [
%__MODULE__{
val: 12
}
]
}
]
},
%__MODULE__{
val: 4
}
]
}
``````

It prints the node in this order:

``````1
2
3
4
5
6
7
9
8
10
12
11
``````
3 Likes

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

How about you start from a simpler example? Printing all the node in the correct order for a tree who has 2 levels (the root node and its children):

``````    %__MODULE__{
val: 1,
children: [
%__MODULE__{val: 2},
%__MODULE__{val: 3},
%__MODULE__{val: 4},
%__MODULE__{val: 5}
]
}
``````