In this LeetCode Q/A an answer w/o any inline comments demonstrates how to accomplish iterative in-order binary tree traversal.
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
traversal = []
node = root
stack = []
while node or stack:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
traversal.append(node.val)
node = node.right
return traversal
Why does this work? I'm primarily confused by the if node statement, which always moves to the left child. The else statement must satisfy the conditions that node does not exist but stack does exist, and this is really perplexing to me.
I'd like to understand it such that I could tweak code to perform pre or post order traversal but not understanding why this code functions, that's a bride too far.
At the start of every iteration of the loop, node represents the root of a subtree that has not yet been visited (at all).
By definition of "in-order traversal", we should first traverse the left subtree of a node, before anything else. So that is why -- when we have the root of an unvisited subtree -- we should go left. At the same time, we take note of the this node, because at some point we will be ready with that left subtree, and then we must be able to find back this node and actually visit it. That is why we push the node on the stack before going left.
When the root of an unvisited subtree has no left child, then node will obviously become None and so in the next iteration we arrive in the else case. There we pop again the parent node from the stack. Now the first thing to do is visit that root (append), and after that we must visit its right subtree, which will be initiated in the next iteration of the loop.