Preorder Traversal of a Binary Tree

Problem Description

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Naive Approach: Recursive Solution

The most straightforward way to perform a preorder traversal is by using recursion. The basic idea is to visit the root node first, then recursively traverse the left subtree, and finally recursively traverse the right subtree.

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


def preorder_recursive(root):
    if root is None:
        return []

    result = [root.val]
    result += preorder_recursive(root.left)
    result += preorder_recursive(root.right)
    return result

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited exactly once.
• Space Complexity: O(N) in the worst case (skewed tree) due to the call stack. In the average case (balanced tree), the space complexity is O(log N).

Optimal Approach: Iterative Solution using a Stack

An iterative solution can be implemented using a stack. The algorithm pushes the root node onto the stack, then repeatedly pops a node, adds its value to the result, and pushes its right and left children onto the stack (right child first to ensure left child is processed first).

def preorder_iterative(root):
    if root is None:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited and processed exactly once.
• Space Complexity: O(N) in the worst case (skewed tree), as the stack can hold up to N nodes. In the average case (balanced tree), the space complexity is O(w), where w is the maximum width of the tree. In the perfect binary tree w = N/2, so it can be written as O(N).

Edge Cases

• Empty Tree: If the root is None, the function should return an empty list. Both the recursive and iterative solutions handle this case correctly.
• Single Node Tree: If the tree contains only the root node, the function should return a list containing only the root's value. Both solutions handle this case.

Code Implementation (Python)

Both recursive and iterative solutions are provided above.