In-order Traversal

Tree Traversal Algorithm: How do you traverse a binary tree in-order (recursively and iteratively)? What are its use cases?

Assume:

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

Iterative

def inorder_iterative(node):
    res = []
    if not node:
        return res
    stack = []
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val) # additional logic here!
        node = node.right
    return res

Recursive

def inorder_recursive(node, res=None):
    if node is None:
        return []
    if res is None:
        res = []
    inorder_recursive(node.left, res)
    res.append(node.val) # additional logic here!
    inorder_recursive(node.right, res)
    return res