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 <= 100Follow up: Recursive solution is trivial, could you do it iteratively?
The goal of Binary Tree Preorder Traversal is to visit nodes in the order Root → Left → Right. A natural way to approach this problem is using Depth-First Search (DFS). Start at the root, record its value, then recursively traverse the left subtree followed by the right subtree. This recursive strategy directly mirrors the preorder definition and is often the simplest to implement.
An alternative approach uses an explicit stack to simulate recursion. Push the root node onto the stack, then repeatedly pop a node, process it, and push its right child followed by its left child. This ensures the left subtree is processed first, maintaining preorder order.
Both methods ensure every node is visited exactly once. The time complexity is O(n) where n is the number of nodes, while space complexity depends on the recursion depth or stack size, which in the worst case can reach O(n) for a skewed tree.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive DFS (Preorder) | O(n) | O(h) average, O(n) worst case |
| Iterative DFS using Stack | O(n) | O(h) average, O(n) worst case |
NeetCode
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.
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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<int> PreorderTraversal(TreeNode root) {
13 List<int> res = new List<int>();
14 Preorder(root, res);
return res;
}
private void Preorder(TreeNode node, List<int> res) {
if (node == null) return;
res.Add(node.val);
Preorder(node.left, res);
Preorder(node.right, res);
}
}This C# script defines a TreeNode class and a solution class with a PreorderTraversal method. It uses recursion to populate a List with the preorder sequence.
The iterative approach replaces the recursive call stack with an explicit stack. Nodes are processed in preorder, using a stack to maintain traversal state.
Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes.
1#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
res.push_back(node->val);
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
return res;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, binary tree traversal problems are very common in FAANG and other top tech company interviews. Preorder traversal is often used to test understanding of recursion, stacks, and depth-first search concepts.
A stack is the most suitable data structure when implementing preorder traversal iteratively. It helps simulate the recursive call stack and ensures nodes are processed in the correct root-left-right order.
The optimal approach is using Depth-First Search following the preorder pattern: root, left, then right. This can be implemented either recursively or iteratively using a stack. Both approaches visit each node exactly once, giving O(n) time complexity.
The difference lies in when the root node is processed. Preorder follows root-left-right, inorder follows left-root-right, and postorder follows left-right-root. Each traversal order is useful for different tree-related problems.
The C++ solution utilizes the STL stack to maintain a record of nodes yet to be explored. The iterative structure eliminates recursion, improving stack safety.