Functional, but not recursive, tree traversal
Does this help?  In your walk_iter, instead of using pop, grab the first element of the stack. Then do something like this ...

if first_element_has_sub_elements:
    new_stack = stack[0][1]
    new_stack.extend(stack[1:])
    stack = new_stack[:]
else:
    stack = stack[1:]


This was my experiment, in case it's helpful ...

TREE = [
 ("L1A", [("L1A2A",), 
          ("L1A2B", [("L1A2B3A", )])]),
 ("L1B", [("L1B2A", [("L1B2A3A", )])]),
 ("L1C",),
 ("L1D", [("L1D2A",), 
          ("L1D2B", [("L1D2B3A", ),
                     ("L1D2B3B",)])]),
 ]

EXPECTED = ["L1A", "L1A2A", "L1A2B", "L1A2B3A",
            "L1B", "L1B2A", "L1B2A3A", "L1C", 
            "L1D", "L1D2A", "L1D2B", "L1D2B3A", "L1D2B3B"]

def traverse_tree(TREE):
    chopped_tree = TREE[:]
    results = []
    while chopped_tree:
        results.append(chopped_tree[0][0])
        if len(chopped_tree[0]) &gt; 1:
            new_tree = chopped_tree[0][1]
            new_tree.extend(chopped_tree[1:])
            chopped_tree = new_tree[:]
        else:
            chopped_tree = chopped_tree[1:]

    return results

if __name__ == "__main__":
    results = traverse_tree(TREE)
    if results == EXPECTED:
        print "OK"
    else:
        print "MISMATCH"
    print "Expected: "
    print EXPECTED
    print "Results: "
    print results