Binary Tree Preorder Traversal

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

Example 1:

Example 2:

Example 3:

Example 4:

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

## Preorder Traversal of a Binary Tree

This problem asks us to implement a preorder traversal of a binary tree. Preorder traversal visits the root node first, then recursively traverses the left subtree, and finally the right subtree.

### 1. Naive Recursive Solution

The most straightforward way to implement preorder traversal is using recursion.

```python
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 not root:
        return []
    
    result = [root.val]
    result.extend(preorder_recursive(root.left))
    result.extend(preorder_recursive(root.right))
    return result

Example:

For the input root = [1, None, 2, 3], the recursive solution will perform the following steps:

1. Visit the root node (1). Add it to the result.
2. Traverse the left subtree (None). It returns an empty list.
3. Traverse the right subtree (2).
   • Visit the root node (2). Add it to the result.
   • Traverse the left subtree (3).
     • Visit the root node (3). Add it to the result.
     • Traverse the left subtree (None). It returns an empty list.
     • Traverse the right subtree (None). It returns an empty list.
   • Traverse the right subtree (None). It returns an empty list.

Finally, it returns [1, 2, 3].

2. Iterative Solution

We can also implement preorder traversal iteratively using a stack.

def preorder_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right child first so left child is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Example:

For the input root = [1, None, 2, 3], the iterative solution will perform the following steps:

1. Push the root node (1) to the stack.
2. While the stack is not empty:
   • Pop the top node (1). Add its value to the result.
   • Push the right child (2) to the stack.
   • Push the left child (None) to the stack (nothing happens since it's None).
   • Pop the top node (2). Add its value to the result.
   • Push the right child (None) to the stack (nothing happens since it's None).
   • Push the left child (3) to the stack.
   • Pop the top node (3). Add its value to the result.
   • Push the right child (None) to the stack (nothing happens since it's None).
   • Push the left child (None) to the stack (nothing happens since it's None).

Finally, it returns [1, 2, 3].

3. Big(O) Runtime Analysis

• Recursive Solution: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
• Iterative Solution: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

4. Big(O) Space Usage Analysis

• Recursive Solution: O(H), where H is the height of the tree. In the worst case (skewed tree), H = N, resulting in O(N) space complexity. In the best case (balanced tree), H = log N, resulting in O(log N) space complexity.
• Iterative Solution: O(H), where H is the height of the tree. In the worst case (skewed tree), H = N, resulting in O(N) space complexity. In the best case (balanced tree), H = log N, resulting in O(log N) space complexity.

5. Edge Cases and Handling

• Empty Tree: If the root is None, 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, return a list containing only the root node's value. Both solutions handle this case correctly.
• Skewed Tree (Left or Right Skewed): The solutions should work correctly for both left and right-skewed trees.