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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12void preorder(TreeNode* root, vector<int>& res) {
13 if (!root) return;
14 res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
preorder(root, res);
return res;
}This C++ implementation uses a vector to store the traversal results. A helper function performs the recursive preorder traversal, ensuring that each node's value is recorded correctly.
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.
1using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> PreorderTraversal(TreeNode root) {
List<int> res = new List<int>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
res.Add(node.val);
if (node.right != null) stack.Push(node.right);
if (node.left != null) stack.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.
C# implementation employs a Stack class to systematically handle traversal. This iteration strategy effectively manages binary trees of all sizes, bypassing recursion limits.