Write entries of a searchtree(non-binary) into a list. (Iterative)

Question

I am trying to write all entries of a search tree into a list. In unchanged order, nodes before children. But I mix the order up somewhere along the way.

def n(value, children=[]):
    return [value,children]

#I want to keep this order in the list
tree = (n(5,[n(2,[n(3)]),n(6),n(8,[n(7),n(9)])]))

def is_empty(tree) :
    return tree == []

def to_list_iter(tree) :

    stack = []
    stack.append(tree)
    l = []
    while stack != [] :
        tree = stack.pop()
        if not is_empty(tree) :
            l.append(tree[0])
            n = len(tree[1])
            while n > 0:
                stack.append(tree[1][len(tree[1])-n])
                n -= 1

    return l

print (to_list_iter(tree))
# This will print the following output:
# [5, 8, 9, 7, 6, 2, 3]
# Instead of the desired [5, 2, 3, 6, 8, 7, 9]

Answer 1

The solution is quite close to your code, though simplified:

def n(value, children=[]):
    return [value,children]

tree = (n(5,[n(2,[n(3)]),n(6),n(8,[n(7),n(9)])]))

def to_list_iter(tree) :

    stack = [tree]
    l = []
    while stack :
        tree = stack.pop()
        if tree:
            l.append(tree[0])
            stack.extend(reversed(tree[1]))

    return l

print (to_list_iter(tree))

The main difference is that you need to extend the stack with a reversed list of children, because the stack is always popped from at the back of the list.