💬 Discord
Sign In
NeetCode #383LC-144EasyTreesNC 250
← Back to All Problems

#383 · #144 · Binary Tree Preorder Traversal(二叉树的前序遍历)

📌 Problem Statement & Constraints

Given the root of a binary tree, return its pre-order traversal (root, left, right) as a list of values. Constraints: the number of nodes is in [0, 100]. The follow-up asks for an iterative solution.

💡 Core Algorithmic Approaches

  1. Push the root, then repeatedly pop and visit.
  2. Push the right child before the left, so the left is popped first and processed next.
  3. This one-stack formulation is the simplest iterative pre-order traversal.
  4. An alternative pushes only the left spine and uses the stack for the right subtrees, which generalises to the other orders.

💻 Benchmark Python3 Implementation

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res = []
        st = [root]
        while st:
            node = st.pop()
            res.append(node.val)
            # push right first so left is processed first
            if node.right:
                st.append(node.right)
            if node.left:
                st.append(node.left)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is pushed and popped once.
💾 Space Complexity
O(h) for the stack in the best case, O(n) in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Pushing left before right: the traversal order would become root, right, left.
  • Recursing without a depth guard: a degenerate tree would exhaust the recursion limit.
  • Forgetting the empty-tree check: st = [root] with root = None would crash on node.val.
  • Assuming the output is sorted: pre-order is determined by the tree structure, not by value.