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:
[0, 100].-100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
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.
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.
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.
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.
Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes.
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.
The idea of using a stack to implement non-recursive traversal is as follows:
stk, and first push the root node into the stack.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.
Python
Java
C++
Go
TypeScript
Morris traversal does not require a stack, and its space complexity is O(1). The core idea is:
Traverse the binary tree nodes,
root is empty, add the current node value to the result list ans, and update the current node to root.right.root is not empty, find the rightmost node pre of the left subtree (which is the predecessor of the root node in inorder traversal):pre is empty, add the current node value to the result list ans, then point the right subtree of the predecessor node to the current node root, and update the current node to root.left.pre is not empty, point the right subtree of the predecessor node to null (i.e., disconnect pre and root), and update the current node to root.right.The time complexity is O(n), where n is the number of nodes in the binary tree. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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. |
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python • NeetCodeIO • 36,308 views views
Watch 9 more video solutions →Practice Binary Tree Preorder Traversal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor