How can i make tree to 2D arrays

Question

I am trying to make tree data structure to 2D array. I am trying to do it with for loop like this. childs() function return child nodes array.

void makeArray(a 1_level_a)
{
    for(2_level_a : 1_level_a.childs())
    {
        for(3_level_a : 2_level_a.childs())
        {

        }
    }
}

How can i do it? any suggestion?

Answer 1

This is a ready-to-run solution that modifies the standard BFS a little and has been tested with multiple levels. The algorithm shifts the previous rows every time multiple children are added from the current node. Also, it keeps track of the total shift when iterating through a particular level to know where to insert blank cells which bubble up from the children. Finally it propagates down placeholder blank nodes for the case when it hits a leaf before the final level of the tree. When our queue is filled only with these dummy nodes we know we can stop.

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

    def add_children(self, children):
        self.children = children


a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")


a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])

arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == ""  for e in queue):
    node = queue[0]
    processed+=1
    children = node.children if len(node.children) > 0 else [Node("")]
    if(to_process==processed):
       arr.append(list(map(lambda x: x.val, children)))
       to_process = len(queue)
       queue+=children
       processed = 0
       shifted = 0
    else:
        arr[-1] += list(map(lambda x: x.val, children))
        queue += children
    queue = queue[1:]
    for i in range(0, len(arr)-1):
        arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
    shifted += len(children)

print("arr: " + str(arr[:-1]))