Binary Tree Preorder Traversal - Video Solutions

Problem Overview: Given the root of a binary tree, return the preorder traversal of its nodes' values. Preorder traversal processes nodes in the order root → left → right, meaning you visit the current node first, then recursively explore the left subtree followed by the right subtree.

Approach 1: Recursive DFS (Time: O(n), Space: O(h))

This approach directly mirrors the definition of preorder traversal. Start from the root, append its value to the result, recursively traverse the left child, then recursively traverse the right child. The recursion implicitly uses the call stack to track traversal state. The algorithm visits each node exactly once, so the time complexity is O(n), where n is the number of nodes. Space complexity is O(h), where h is the height of the tree due to the recursion stack (worst case O(n) for a skewed tree, O(log n) for balanced trees). This method is concise and ideal when recursion depth is manageable. It relies on Depth-First Search concepts applied to a Binary Tree.

Approach 2: Iterative Traversal Using Stack (Time: O(n), Space: O(h))

The iterative solution simulates the recursion stack using an explicit stack. Push 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. Pushing the right child first ensures the left child is processed next, preserving preorder order (root → left → right). Each node is pushed and popped at most once, resulting in O(n) time complexity. The stack holds at most O(h) nodes at a time, where h is the tree height. This approach avoids recursion and works well in environments where recursion depth may cause stack overflow.

Recommended for interviews: Interviewers typically expect the recursive DFS solution first because it demonstrates understanding of preorder traversal and tree recursion. The iterative stack approach shows deeper knowledge of how recursion works internally and proves you can convert recursive tree algorithms into iterative ones. Showing both solutions signals strong mastery of tree traversal patterns.