Problem Description

You are given the root of a binary tree. Your task is to return a list containing the values of all nodes in the tree following a preorder traversal pattern.

In preorder traversal, you visit nodes in this specific order:

1. First, visit the root node (current node)
2. Then, traverse the entire left subtree
3. Finally, traverse the entire right subtree

For example, if you have a binary tree like this:

      1
     / \
    2   3
   / \
  4   5

The preorder traversal would visit nodes in this sequence: 1 → 2 → 4 → 5 → 3, resulting in the output [1, 2, 4, 5, 3].

The solution uses a recursive depth-first search (DFS) approach. The dfs helper function:

• Checks if the current node is None (base case)
• If not, it adds the current node's value to the result list ans
• Recursively calls itself on the left child
• Recursively calls itself on the right child

This naturally follows the preorder pattern: root → left → right. The recursion handles the tree traversal automatically by maintaining the call stack, ensuring all nodes are visited in the correct order.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure, which is a hierarchical data structure with a root node and no cycles.

DFS

• Since we answered "yes" to the tree question, the flowchart leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS (Depth-First Search) for traversing the binary tree. This perfectly aligns with the preorder traversal requirement, as preorder traversal is inherently a depth-first approach where we:

1. Visit the current node first
2. Recursively explore the left subtree completely
3. Then recursively explore the right subtree completely

DFS is the natural choice for tree traversal problems, especially when we need to visit nodes in a specific order like preorder (root → left → right). The recursive nature of DFS makes it straightforward to implement the traversal pattern by processing the current node and then recursively calling the function on the left and right children.

Intuition

When we need to traverse a binary tree and collect node values in a specific order, we need to think about how we naturally explore the tree structure. Preorder traversal follows a "root-first" pattern - we want to process the current node before exploring its children.

Think of it like reading a book's table of contents: you read the chapter title first, then all its subsections on the left, and finally the subsections on the right. This natural top-down, left-to-right exploration is exactly what preorder traversal captures.

The recursive approach mirrors this intuitive process perfectly. At each node, we perform three simple actions in sequence:

1. Record the current node's value (visit the root)
2. Explore everything in the left subtree
3. Explore everything in the right subtree

This pattern naturally emerges when we think recursively: "What do I do at this node?" The answer is always the same - process myself first, then handle my left child's entire subtree, then my right child's entire subtree. The recursion stack automatically keeps track of where we are and ensures we return to parent nodes after fully exploring their children.

The beauty of this approach is that each recursive call handles a smaller version of the same problem - traversing a subtree in preorder. The base case (when we hit a None node) stops the recursion, and as the call stack unwinds, we naturally visit all nodes in the correct preorder sequence.

By using a shared list ans that persists across all recursive calls, we can collect the values as we visit each node, building our final result incrementally as we traverse the tree.

Solution Approach

The solution implements a recursive traversal using Depth-First Search (DFS) to visit all nodes in preorder sequence.

Key Components:

1. Helper Function (dfs): We define an inner recursive function that handles the traversal logic. This function:

   • Takes a node as input
   • Checks if the node is None (base case) - if so, returns immediately
   • Processes the current node by appending its value to the result list
   • Recursively traverses the left subtree
   • Recursively traverses the right subtree

2. Result Container (ans): We initialize an empty list before starting the traversal. This list is accessible within the nested dfs function and accumulates node values as we traverse.

Step-by-Step Execution:

def dfs(root):
    if root is None:    # Base case: empty node
        return
    ans.append(root.val)  # Visit root (preorder)
    dfs(root.left)        # Traverse left subtree
    dfs(root.right)       # Traverse right subtree

The algorithm follows these steps:

1. Start with the root node
2. If the current node exists, add its value to ans
3. Recursively process the entire left subtree (this will add all left subtree values to ans in preorder)
4. Recursively process the entire right subtree (this will add all right subtree values to ans in preorder)
5. Return the completed list

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, representing the maximum recursion depth. In the worst case (skewed tree), this could be O(n).

The recursive approach naturally maintains the call stack, ensuring we return to parent nodes after completing their subtrees, thus achieving the desired preorder traversal pattern: root → left → right.

Example Walkthrough

Let's trace through the algorithm with a small binary tree to see how the preorder traversal works step by step.

Consider this tree:

      1
     / \
    2   3
   /
  4

Initial Setup:

• ans = [] (empty result list)
• Start with dfs(root) where root has value 1

Execution Trace:

Step 1: Call dfs(node 1)

• Node is not None, so continue
• Append 1 to ans: ans = [1]
• Call dfs(node 1.left) → This is node 2

Step 2: Call dfs(node 2)

• Node is not None, so continue
• Append 2 to ans: ans = [1, 2]
• Call dfs(node 2.left) → This is node 4

Step 3: Call dfs(node 4)

• Node is not None, so continue
• Append 4 to ans: ans = [1, 2, 4]
• Call dfs(node 4.left) → This is None

Step 4: Call dfs(None)

• Node is None, so return immediately
• Back to Step 3, now call dfs(node 4.right) → This is also None

Step 5: Call dfs(None)

• Node is None, so return immediately
• Node 4 is complete, return to Step 2

Step 6: Back in dfs(node 2), now call dfs(node 2.right) → This is None

• Node is None, so return immediately
• Node 2 is complete, return to Step 1

Step 7: Back in dfs(node 1), now call dfs(node 1.right) → This is node 3

Step 8: Call dfs(node 3)

• Node is not None, so continue
• Append 3 to ans: ans = [1, 2, 4, 3]
• Call dfs(node 3.left) → This is None
• Call dfs(node 3.right) → This is None
• Node 3 is complete, return to Step 1

Step 9: All recursive calls complete

• Final result: ans = [1, 2, 4, 3]

Notice how the values are added to the result list in the exact order we visit them: root first (1), then entire left subtree (2, 4), then entire right subtree (3). The recursion stack naturally handles returning to parent nodes after exploring their children completely.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once during the traversal. For each node visit, the algorithm performs a constant amount of work - appending the node's value to the result list and making recursive calls to its children. Since we visit all n nodes exactly once and perform O(1) work at each node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of two components:

1. Recursive call stack: In the worst case (a skewed tree where each node has only one child), the recursion depth can reach n, requiring O(n) stack space. In the best case (a balanced tree), the recursion depth would be O(log n), but we consider the worst-case scenario for complexity analysis.
2. Output array: The ans list stores all n node values, requiring O(n) space. However, this is often not counted as auxiliary space since it's required for the output.

The dominant factor is the recursive call stack space, which in the worst case is O(n). Therefore, the overall space complexity is O(n).

Common Pitfalls

1. Modifying the Result List Inside Recursive Calls

A common mistake is passing the result list as a parameter to the recursive function and trying to return it, which can lead to confusion about when and how to return values.

Incorrect Approach:

def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    def traverse(node, result):
        if node is None:
            return result  # Problematic: multiple return points
        result.append(node.val)
        result = traverse(node.left, result)   # Unnecessary assignment
        result = traverse(node.right, result)  # Unnecessary assignment
        return result
  
    return traverse(root, [])

Why it's problematic: While this might work, it's unnecessarily complex and can cause confusion about the return value. The assignments are redundant since lists are mutable and passed by reference.

Better Solution: Use the closure pattern (as shown in the original solution) where the result list is defined in the outer scope and modified by the inner function without needing to pass or return it.

2. Forgetting to Handle Empty Tree

Another pitfall is not properly handling the case when the root itself is None.

Problematic Code:

def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    result = [root.val]  # Error if root is None!
  
    def traverse(node):
        if node.left:
            result.append(node.left.val)
            traverse(node.left)
        if node.right:
            result.append(node.right.val)
            traverse(node.right)
  
    traverse(root)
    return result

Solution: Always check if the root is None before accessing its properties. The original solution handles this correctly by checking if node is None at the beginning of the recursive function.

3. Using Global Variables Instead of Closure

Problematic Approach:

result = []  # Global variable - bad practice!

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        global result
        result = []  # Need to reset for each call
        self.traverse(root)
        return result
  
    def traverse(self, node):
        global result
        if node:
            result.append(node.val)
            self.traverse(node.left)
            self.traverse(node.right)

Why it's problematic:

• Global variables persist between function calls, causing incorrect results if the function is called multiple times
• Makes the code harder to test and debug
• Violates encapsulation principles

Solution: Keep the result list local to the function and use either closure (nested function) or pass it as a parameter properly.

4. Iterative Solution Memory Management

When implementing an iterative solution using a stack, a common mistake is pushing None nodes onto the stack:

Problematic Iterative Approach:

def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
  
    stack = [root]
    result = []
  
    while stack:
        node = stack.pop()
        result.append(node.val)
        stack.append(node.right)  # Could be None!
        stack.append(node.left)   # Could be None!
  
    return result

Better Iterative Solution:

def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
  
    stack = [root]
    result = []
  
    while stack:
        node = stack.pop()
        result.append(node.val)
      
        # Only push non-None nodes
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
  
    return result

This prevents unnecessary iterations and potential errors when trying to access properties of None nodes.