Binary Tree Traversal Template

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, node: TreeNode) -> List[int]:
        
        stack = []
        res = []
        
        '''
        Initial State:
        node: Not None
        stack: Empty
        
        Final State:
        node: None
        Stack: Empty
        
        Stack is used to save node before exploring to its left.
        Stack "remembers" the parent before continuing to explore.
        So that I can backtrack when I hit the leaf node.
        
        Preorder and Inorder
        Once I finish exploring the left, get latest reference to parent
        For In-order, perform work on this parent (LcR).
        Now explore the right.
        
        In recursion, backtracking happens when you return at the top (at the base case).
        
        '''
        
        while node is not None or stack:
            # until I reach a leaf node, traverse left and come back to node to then explore right
            isNotFinishedExploringLeft = node is not None
            
            # Preorder: NLR
            # Inorder: LNR
            # Postorder: LRN
            
            if isNotFinishedExploringLeft:
                # PREORDER Work
                
                # Saving me as the parent
                stack.append((node, False))
                # Exploring Left
                node = node.left
            else:
                # I have finished exploring the left.
                
                # Backtrack to my parent
                temp, isRightVisited = stack.pop()
                
                # PostOrder Logic
                if isRightVisited:
                    # POSTORDER Work
                else:
                    stack.append((node, True))
                    node = temp.right
                    
                # INORDER Work
                # Go to the right
                # node = temp.right
                
                
        
        return res