Tree Traversal Python Cheatsheet

Tree Traversal Cheatsheet

1. Preorder Traversal (Root ➝ Left ➝ Right)

Recursive way

def preorder_traversal(root):
    if root is None:
        return []
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)

Iterative way

def preorder_traversal_iterative(root):
    if not root:
        return []
    stack, output = [root], []
    while stack:
        node = stack.pop()
        output.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return output

2. Inorder Traversal (Left ➝ Root ➝ Right)

Recursive way

def inorder_traversal(root):
    if root is None:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

Iterative way

def inorder_traversal_iterative(root):
    stack, output = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        output.append(current.val)
        current = current.right
    return output

3. Postorder Traversal (Left ➝ Right ➝ Root)

Recursive way

def postorder_traversal(root):
    if root is None:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]

Iterative way

def postorder_traversal_iterative(root):
    if not root:
        return []
    stack, output = [root], []
    while stack:
        node = stack.pop()
        output.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return output[::-1]  # reverse the result

Time Complexity: O(n)

Space Complexity: O(n)