LeetCode Solutions Blog

Binary Tree Preorder Traversal

Number: 144

Difficulty: Easy

Paid? No

Problem Description

Given the root of a binary tree, return the preorder traversal of its nodes' values. In preorder traversal, you visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.

Key Insights

Preorder traversal follows the order: Root -> Left -> Right.
A recursive solution is straightforward but the problem asks for an iterative solution.
Use a stack to simulate the recursive function call behavior.
When using a stack, push the right child first so that left is processed before right.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes, because every node is visited once. Space Complexity: O(N) in the worst case due to the stack when the tree is unbalanced.

Solution

We use an iterative approach with a stack. Start by pushing the root to the stack. While the stack is not empty, pop the top node from the stack, record its value, and push its right child (if exists) followed by its left child (if exists) to the stack. This ensures that the left child is processed before the right child, adhering to the preorder traversal order.

Code Solutions

# 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

def preorderTraversal(root):
    # List to store the preorder traversal
    result = []
    
    # Edge case: if the tree is empty, return an empty list
    if not root:
        return result

    # Initialize stack with the root node
    stack = [root]

    # Iterate while the stack is not empty
    while stack:
        # Pop the top node from the stack
        node = stack.pop()
        # Add the node's value to the result list
        result.append(node.val)
        
        # Push the right child first if it exists (stack LIFO ensures left is processed next)
        if node.right:
            stack.append(node.right)
        # Push the left child if it exists
        if node.left:
            stack.append(node.left)
    
    # Return the result list containing preorder traversal
    return result