Domain 2MediumCORE

Binary Tree Preorder Traversal

We are given the root of a binary tree and need to return an array representing its preorder traversal. Preorder means we visit nodes in this specific order for every subtree: Root, then Left Child, then Right Child.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Stack#Tree

144. Binary Tree Preorder Traversal

Model: qwen3.5:9b
Topics: Stack,Tree
FAANG asked: 1
Acceptance rate: 57.8%


Problem Breakdown

We are given the root of a binary tree and need to return an array representing its preorder traversal. Preorder means we visit nodes in this specific order for every subtree: Root, then Left Child, then Right Child.

Inputs: A pointer/reference to the root node (or null if empty). Outputs: A list of integers containing values from root down, left-to-right at each level.

Implicit Constraints & Edge Cases:

  • The tree can be unbalanced or skewed.
  • Nodes have integer values which may be negative (-100 <= Node.val).
  • Empty Tree: If root is null/None, the output must be an empty list []. This is a critical base case to handle before processing nodes.

Intuition

The definition of preorder traversal (Root -> Left -> Right) naturally maps to Depth-First Search (DFS).

  1. Recursive Approach: The most direct way is recursion: visit the current node, recurse on left child if it exists, then recurse on right child. This works perfectly and handles edge cases implicitly via base case checks (if not root).
  2. Iterative Requirement: However, interviewers often ask for an iterative solution to avoid stack overflow risks (though less of a concern here with N=100) or simply to demonstrate understanding of how function calls are managed internally using the call stack.
  3. Key Insight: To simulate recursion iteratively, we need our own explicit stack. Since it’s DFS, we push nodes onto the stack and pop them when ready to process. Because a Stack is LIFO (Last-In-First-Out), if we want to visit Left before Right after processing Root, we must push Right first, then Left. This ensures Left sits on top of the stack and gets popped next.

Approach

  1. Initialize an empty list result for output and a stack data structure (using Python’s list).
  2. Check if root is null; return [] immediately to handle the empty tree case efficiently.
  3. Push the root node onto the stack.
  4. While the stack is not empty:
    • Pop a node from the top of the stack and append its value to result.
    • If this popped node has a right child, push it to the stack (if non-null).
    • If this popped node has a left child, push it to the stack (if non-null).
  5. The order matters: Pushing Right then Left ensures we process Left first in subsequent iterations because of LIFO behavior.

Complexity Analysis

  • Time Complexity: O(N)O(N) where N is the number of nodes. We visit every node exactly once, pushing and popping it from the stack at most twice (once for each child check).
  • Space Complexity: O(H)O(H). In Python list used as a stack, we store pointers to nodes in memory proportional to the height of the tree. Worst case is a skewed line-like tree where space becomes O(N)O(N); best case (balanced) is O(log⁡N)O(\log N). Note that unlike BFS which depends on width (WW), DFS iterative traversal depth strictly follows the path from root, so it does not depend on the number of nodes at any level.

Solution

from typing import List

# Assuming standard LeetCode TreeNode definition exists:
# 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]:
        # Handle empty tree edge case immediately
        if not root:
            return []
        
        result = []
        stack = [root]  # Initialize with the root node
        
        while stack:
            current_node = stack.pop()
            
            # Add value to traversal list (Preorder step)
            result.append(current_node.val)
            
            # Push right child first, then left child. 
            # This ensures we visit Left before Right due to LIFO property of the stack.
            if current_node.right:
                stack.append(current_node.right)
            if current_node.left:
                stack.append(current_node.left)
                
        return result

Edge Cases Handled

  • Empty Tree (root = None): The initial if not root: check returns an empty list immediately, preventing errors on accessing .val.
  • Single Node: Pushes the single node, pops it once, appends value. Loop terminates correctly with [value].
  • Skewed Trees (Left-heavy or Right-heavy):
    • Left-skewed: Stack depth grows to N, but logic holds as we push right (None) and left (Node).
    • Right-skewed: Same behavior; stack handles the chain of nodes correctly.
  • Null Children: The if current_node.right checks ensure we don’t try to append None values or crash on missing attributes.