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
rootis 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).
- 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). - 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.
- 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
- Initialize an empty list
resultfor output and astackdata structure (using Python’slist). - Check if
rootis null; return[]immediately to handle the empty tree case efficiently. - Push the root node onto the stack.
- 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).
- Pop a node from the top of the stack and append its value to
- The order matters: Pushing Right then Left ensures we process Left first in subsequent iterations because of LIFO behavior.
Complexity Analysis
- Time Complexity: 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: . In Python
listused 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 ; best case (balanced) is . Note that unlike BFS which depends on width (), 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 initialif 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.rightchecks ensure we don’t try to append None values or crash on missing attributes.