Iterative Inorder Traversal of BST

IterativeInorderBSTTraversal.py

from typing import List, Optional

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def inorder_traversal(root: Optional['TreeNode']) -> List[int]:
    # holds the inorder result
    res = []
    # manual stack for traversal
    stack = []
    # traversal pointer
    curr = root

    # process nodes while there are pending nodes or a current one
    while curr is not None or stack:
        # descend to the leftmost node
        while curr is not None:
            # push node for later
            stack.append(curr)
            # move left
            curr = curr.left

        # the next node to visit
        curr = stack.pop()
        # record its value
        res.append(curr.val)
        # then process its right subtree
        curr = curr.right

    # final inorder sequence
    return res