Iterative tree traversal to turn tree into a dictionary and list I am trying to iteratively turn a tree into a list.

For example:


                   c1
              c11        c12
          c111   c112



The tree above should return:

        [
            {'value': 'c1', 'children': 
                [
                    {'value': 'c12', 'children': []} , 
                    {'value': 'c11', 'children': 
                        [
                            {'value': 'c112', 'children': []}, 
                            {'value': 'c111', 'children': []}
                        ]
                ]
            }
        ]


Below is my code and here is gist for clearer viewing:

class Node():
    def __init__(self, node_list, value):
        self.node_list = node_list
        self.value = value


def reconstruct_iteratively(root):

    stack = list()

    # A tuple that stores node to be traverse and the layer the node is in
    node_tuple = (root, 0)
    stack.append(node_tuple)

    layer = 0
    pre_layer = 0
    level = dict()

    # This is a postorder traversal
    while len(stack) != 0:
        # This case catch the event that next node is the parent layer and this node is not 
        #     a termination node

        if node_tuple[1] &lt; pre_layer - 1:
            parent_node = stack.pop()
            parent_node_dict = {'value': parent_node[0].value, 'children': level.pop(layer, None)}
            pre_layer = layer
            layer -= 1

            if layer in level:
                level[layer].append(parent_node_dict)
            else:
                level[layer] = [parent_node_dict]

            if len(stack) != 0:
                node_tuple = stack[-1]

        # This case catch the event for traversing down to the child
        elif node_tuple[0].node_list is not None:
            for child in node_tuple[0].node_list:
                stack.append((child, layer + 1))
            node_tuple = (node_tuple[0].node_list[-1], layer + 1)
            layer += 1
        # This case catch the event that we are at the termination node
        elif node_tuple[0].node_list is None:
            old_node = stack.pop()
            node_dict = {'value': old_node[0].value, 'children': []}
            node_tuple = stack[-1]

            # Two possible scenario
            # 1. The next node is in the same layer
            # 2. The next node is in the parent layer
            if node_tuple[1] == layer:
                if layer in level:
                    level[layer].append(node_dict)
                else:
                    level[layer] = [node_dict]
            else:
                if layer in level:
                    level[layer].append(node_dict)
                else:
                    level[layer] = [node_dict]

                parent_node = stack.pop()
                parent_node_dict = {'value': parent_node[0].value, 'children': level.pop(layer, None)}
                pre_layer = layer
                layer -= 1 

                if layer in level:
                    level[layer].append(parent_node_dict)
                else:
                    level[layer] = [parent_node_dict]

                if len(stack) != 0:
                    node_tuple = stack[-1]

    return [parent_node_dict]


I am looking for advices to make the code clearer and more efficient. Any comment would be appreciated. 

Thanks
Some suggestions:

Empty lists are False, so while len(stack) != 0 is the same as while stack.  None is also False, so you can check for empty lists and None values at the same time.

You can use dict.setdefault to get a value and set it to a default (in your case an empty list). if it isn't already there.

You can convert an append loop to extend with a generator expression, or better yet just a zip.

Your last two elif tests are mutually exclusive, so the last can be an else.

The if node_tuple[1] == layer: test does the same thing in the first line of both cases.  I  moved that out of the if test, but if they are supposed to do something different you should fix that yourself.

pre_layer always has its value subtracted by one, so it is easier to subtract one before defining it.

You always set node_tuple to stack[-1] if stack is non-empty, so you can move that out  of the if test entirely.  And if you put it at the beginning of the loop, you can avoid the if test entirely.  You can simplify this further by only getting it if you need it.

def reconstruct_iteratively(root):
    # A tuple that stores node to be traverse and the layer the node is in
    stack = [(root, 0)]

    layer = 0
    pre_layer = -1
    level = dict()

    # This is a postorder traversal
    while stack:
        node_value, node_layer = stack[-1]
        node_list = node_value.node_list
        # This case catch the event that next node is the parent layer and
        # this node is not a termination node
        if node_layer &lt; pre_layer:
            parent_node = stack.pop()
            parent_node_dict = {'value': parent_node[0].value, 
                                'children': level.pop(layer, None)}
            layer -= 1
            pre_layer = layer

            level.setdefault(layer, []).append(parent_node_dict)

        # This case catch the event for traversing down to the child
        elif node_list:
            stack.extend(zip(node_list, [layer+1]*len(node_list)))
            layer += 1

        # This case catch the event that we are at the termination node
        else:
            # Two possible scenario
            # 1. The next node is in the same layer
            # 2. The next node is in the parent layer
            level.setdefault(layer, []).append({'value': node_value.value, 
                                                'children': []})
            del stack[-1]
            if stack[-1][1] != layer:
                parent_node_dict = {'value': stack.pop()[0].value, 
                                    'children': level.pop(layer, None)}
                layer -= 1 
                pre_layer = layer

                level.setdefault(layer, []).append(parent_node_dict)

    return [parent_node_dict]