White RoomNEW

What The Stack Holds

The iterative inorder walk, with an explicit stack instead of recursion:

def inorder(root):
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right
    return out

Run on this tree:

        5
       / \
      3   8
     / \  /
    2   4 7

At the instant out first reaches length 3, what does stack hold, listed bottom to top?