Level Order Traversal of N-ary Tree

Questions / Help
1

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:

TREE
TREE604×886 38 KB

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 :slightly_frowning_face:

2

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 :pray:. 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
3

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.

4

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 :+1:

5

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}
      ]
    }

I think, this could help you. Then, you’ll be able to build your solution from this simple example, and add more levels.

2 Likes
6

Thats great advice. Thank you!

7

Hi @bazybaz,

I had a similar need recently and found this lib nary_tree. The code is a great source fo information and helped me.

Andrew

1 Like