Binary Tree Preorder Traversal - Solution & Explanation
Problem Statement
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,2,3]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [1,2,4,5,6,7,3,8,9]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Approach Overview
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.
Approach 1: Recursive Approach
The recursive approach naturally aligns with the definition of preorder traversal: visit the root first, then recursively traverse the left subtree, followed by the right subtree.
This C code defines a recursive function for the preorder traversal. It allocates space for the result and uses a helper function to populate the preorder values by traversing each node recursively.
Complexity
Time Complexity: O(N) where N is the number of nodes, as each node is visited once. Space Complexity: O(N) in the worst case due to recursion stack space.
Approach 2: Iterative Approach using Stack
The iterative approach replaces the recursive call stack with an explicit stack. Nodes are processed in preorder, using a stack to maintain traversal state.
In C, we use an array to simulate a stack, manually pushing and popping nodes while traversing the tree. Nodes are visited and added to the result list in prenode order.
Complexity
Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes.
Approach 3: Recursive Traversal
We first visit the root node, then recursively traverse the left and right subtrees.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space used for recursive calls.
Approach 4: Stack Implementation for Non-Recursive Traversal
The idea of using a stack to implement non-recursive traversal is as follows:
- Define a stack
stk, and first push the root node into the stack. - If the stack is not empty, pop a node from the stack each time.
- Process the node.
- First push the right child of the node into the stack, then push the left child of the node into the stack (if there are child nodes).
- Repeat steps 2-4.
- Return the result.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree. The space complexity mainly depends on the stack space.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Morris Preorder Traversal
Morris traversal does not require a stack, and its space complexity is O(1). The core idea is:
Traverse the binary tree nodes,
- If the left subtree of the current node
rootis empty, add the current node value to the result listans, and update the current node toroot.right. - If the left subtree of the current node
rootis not empty, find the rightmost nodepreof the left subtree (which is the predecessor of therootnode in inorder traversal):- If the right subtree of the predecessor node
preis empty, add the current node value to the result listans, then point the right subtree of the predecessor node to the current noderoot, and update the current node toroot.left. - If the right subtree of the predecessor node
preis not empty, point the right subtree of the predecessor node to null (i.e., disconnectpreandroot), and update the current node toroot.right.
- If the right subtree of the predecessor node
- Repeat the above steps until the binary tree node is null, and the traversal ends.
The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(N) where N is the number of nodes, as each node is visited once. Space Complexity: O(N) in the worst case due to recursion stack space. |
| Iterative Approach using Stack | Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes. |
| Recursive Traversal | — |
| Stack Implementation for Non-Recursive Traversal | — |
| Morris Preorder Traversal | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Best for clarity and when recursion depth is safe. Mirrors preorder definition. |
| Iterative Using Stack | O(n) | O(h) | Preferred when avoiding recursion or when explicit control of traversal stack is needed. |
Video Solution
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python • NeetCodeIO • 38,612 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Preorder Traversal easy or hard?
Binary Tree Preorder Traversal Python/Java solution
How to solve Binary Tree Preorder Traversal in O(n)?
What is the best approach for Binary Tree Preorder Traversal?
Is Binary Tree Preorder Traversal asked at Google/Amazon/Meta?
What data structure is used in Binary Tree Preorder Traversal?
What is the time complexity of Binary Tree Preorder Traversal?
Ready to solve this problem?
Practice Binary Tree Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCode