Binary Tree Preorder Traversal easy

Problem Statement

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

Example 1

Input: root = [1,null,2,3] Output: [1,2,3]

Example 2

Input: root = [] Output: []

Steps

The preorder traversal of a binary tree follows the order: Root -> Left -> Right. We'll implement this using a recursive approach and then an iterative approach using a stack.

Recursive Approach:

1. Base Case: If the root is None (empty tree), return an empty list.
2. Recursive Step:
   • Add the root's value to the result list.
   • Recursively traverse the left subtree and append the result to the list.
   • Recursively traverse the right subtree and append the result to the list.

Iterative Approach:

1. Initialize an empty stack and an empty result list.
2. Push the root node onto the stack.
3. While the stack is not empty:
   • Pop a node from the stack.
   • Add the node's value to the result list.
   • Push the right child (if it exists) onto the stack.
   • Push the left child (if it exists) onto the stack (important: left child first for correct order).

Explanation

Recursive Approach: The recursive approach directly mirrors the definition of preorder traversal. It's concise but might lead to stack overflow errors for very deep trees.

Iterative Approach: The iterative approach avoids recursion by using a stack to simulate the function call stack. This makes it more memory-efficient for deep trees, avoiding potential stack overflow issues. The order of pushing the right and left children onto the stack is crucial to maintain the correct preorder traversal.

Code

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def preorderTraversal(self, root: TreeNode) -> list[int]:
        #Recursive Approach
        result = []
        def traverse(node):
            if not node:
                return
            result.append(node.val)
            traverse(node.left)
            traverse(node.right)
        traverse(root)
        return result


        #Iterative Approach (more efficient for very deep trees)
        # result = []
        # stack = [root]
        # while stack:
        #     node = stack.pop()
        #     if node:
        #         result.append(node.val)
        #         stack.append(node.right)
        #         stack.append(node.left)
        # return result

Complexity

Recursive Approach:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N.

Iterative Approach:

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W could be N. However, it's generally better than the recursive approach's space complexity for deep trees.