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?
Sign in to answer questions and track your progress
Sign In