Iterative binary tree inorder traversal python

Question

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.

Just take a piece of paper and a small example tree and work it out on paper. — trincot
– trincot, Commented May 10, 2022 at 20:50

trincot · Accepted Answer · 2022-05-11 08:31:01Z

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.

Collectives™ on Stack Overflow

Iterative binary tree inorder traversal python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related