A decent way to do real iterative tree traversal

[csujedihy]

For three different kinds of traversal, we only need to change the order of tuples in one line just like what we've done in the recursive solution which is very decent and classical. Just put (0, p[1]) in different order!

The idea is from my former lab-mate and it's actually a BFS but changing the order on queue when traversing to emulate DFS.

For post-order traversal:

def postorderTraversal(self, root):
    res, stack = [], [(1, root)]
    while stack:
        p = stack.pop()
        if not p[1]: continue
        stack.extend([(0, p[1]), (1, p[1].right), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
    return res

For in-order traversal:

def inorderTraversal(self, root):
    res, stack = [], [(1, root)]
    while stack:
        p = stack.pop()
        if not p[1]: continue
        stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
    return res

For pre-order traversal:

def preorderTraversal(self, root):
    res, stack = [], [(1, root)]
    while stack:
        p = stack.pop()
        if not p[1]: continue
        stack.extend([(1, p[1].right), (1, p[1].left), (0, p[1])]) if p[0] != 0 else res.append(p[1].val)
    return res

[chu-tianshu]

Amazing