Binary Tree Preorder Traversal - Solution & Explanation

Problem Overview: Given the root of a binary tree, return the preorder traversal of its node values. Preorder means you process nodes in the order root → left → right. The task checks your understanding of tree traversal and depth-first exploration patterns.

Approach 1: Recursive DFS Traversal (O(n) time, O(h) space)

The recursive approach follows the natural definition of preorder traversal: visit the current node, recursively traverse the left subtree, then recursively traverse the right subtree. You start at the root, append its value to the result list, and call the same function on node.left and node.right. Each node is processed exactly once, giving O(n) time complexity where n is the number of nodes. The recursion stack uses O(h) space, where h is the height of the tree (worst case O(n) for a skewed tree, O(log n) for a balanced tree). This approach maps directly to the definition of preorder and is usually the shortest and most readable implementation when recursion is allowed. It also reinforces the core idea of depth-first search in trees.

Approach 2: Iterative Traversal Using Stack (O(n) time, O(h) space)

The iterative solution simulates the recursion stack using an explicit stack. Start by pushing the root node onto the stack. While the stack is not empty, pop the top node, record its value, then push its right child followed by its left child. The push order matters: pushing the right child first ensures the left child is processed next, preserving preorder order (root → left → right). Each node enters and leaves the stack once, so the time complexity remains O(n). The stack holds at most the height of the tree at any time, giving O(h) auxiliary space. This approach is useful when recursion depth could cause stack overflow or when interviewers want to see how you convert recursive DFS logic into an iterative algorithm.

Recommended for interviews: Both approaches are acceptable, but interviewers often expect you to start with the recursive DFS because it directly reflects preorder traversal logic. After that, showing the iterative stack-based solution demonstrates deeper understanding of how recursion works under the hood. The recursive version proves you understand traversal order, while the stack-based version shows you can control the traversal manually using fundamental data structures.