Log inSign up
easyleetcodeNot Started

Binary Tree Preorder Traversal

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, return the preorder traversal of its nodes' values.

In preorder traversal, nodes are visited in the order: Root -> Left -> Right.

Example 1 · Example 1: Standard Tree:

Input: root = [1, null, 2, 3]
Output: [1, 2, 3]
Explanation: Visiting root (1), then right subtree: root (2), left child (3) -> [1, 2, 3].

Example 2 · Example 2: Empty Tree:

Input: root = []
Output: []
Explanation: The tree is empty, so traversal is empty.

Example 3 · Example 3: Single Node:

Input: root = [1]
Output: [1]
Explanation: Only root node exists.

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the recursive structure of preorder DFS.
  • Implement the iterative stack approach with inverted push ordering.
  • Learn the concept of Morris traversal for O(1) auxiliary space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Traverse binary tree visiting root before subtrees.
  • Prefix serialization or tree cloning.

Algorithmic Decision Tree:

  • If tree is empty (root == null), return [].
  • Recursive: visit(node.val), dfs(node.left), dfs(node.right).
  • Iterative Stack: push root; pop node, append val, push right, push left.

Connected Patterns:

Binary Tree Inorder TraversalBinary Tree Postorder TraversalBinary Tree Level Order Traversal

1. Recursive DFS Preorder Traversal

Intuition

Define a recursive helper function that takes the current node. If node is null, return. Append node.val to result. Recursively call helper(node.left), then helper(node.right).

When to apply: Default standard implementation when call stack space is acceptable.

Algorithm

  1. Step 1: If root is null, return empty list.
  2. Step 2: Process current node value: append root.val to result.
  3. Step 3: Recursively traverse left child.
  4. Step 4: Recursively traverse right child.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* root, vector<int>& ans) {
10 if (!root) return;
11 ans.push_back(root->val);
12 dfs(root->left, ans);
13 dfs(root->right, ans);
14 }
15 vector<int> preorderTraversal(TreeNode* root) {
16 vector<int> ans;
17 dfs(root, ans);
18 return ans;
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n) — Every node is visited exactly once, taking O(n) time. Call stack takes O(h) memory where h is tree height (O(log n) balanced, O(n) worst case).
  • Space complexity: O(h) — Recursion call stack takes O(h) space.

2. Iterative Stack Traversal

Intuition

Initialize an empty stack and push root. While stack is not empty: pop node, add node.val to result. If node.right exists, push node.right. If node.left exists, push node.left (pushed second so it is popped first).

When to apply: When avoiding recursion to prevent potential stack overflow on deeply skewed trees.

Algorithm

  1. Step 1: If root is null, return empty list.
  2. Step 2: Initialize stack and push root.
  3. Step 3: While stack is non-empty:
  4. - Pop node from stack, record node.val.
  5. - If node.right != null, push node.right.
  6. - If node.left != null, push node.left.
  7. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> preorderTraversal(TreeNode* root) {
10 vector<int> ans;
11 if (!root) return ans;
12 stack<TreeNode*> st;
13 st.push(root);
14 while (!st.empty()) {
15 TreeNode* node = st.top();
16 st.pop();
17 ans.push_back(node->val);
18 if (node->right) st.push(node->right);
19 if (node->left) st.push(node->left);
20 }
21 return ans;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — Each node is pushed and popped exactly once, taking O(n) time.
  • Space complexity: O(h) — Stack holds at most O(h) nodes at any time.

3. Morris Preorder Traversal (Threaded Binary Tree)

Intuition

For current node: if left is null, record current.val and move current = current.right. Otherwise, find inorder predecessor (rightmost node in left subtree). If predecessor.right is null, record current.val (preorder visit!), create thread predecessor.right = current, and move current = current.left. If predecessor.right == current, cut thread predecessor.right = null, and move current = current.right.

When to apply: When strictly O(1) auxiliary space (excluding result) is required.

Algorithm

  1. Step 1: Set curr = root.
  2. Step 2: While curr != null:
  3. - If curr.left == null: add curr.val, curr = curr.right.
  4. - Else:
  5. * Find pred = curr.left, while pred.right != null && pred.right != curr: pred = pred.right.
  6. * If pred.right == null: add curr.val (visit), set pred.right = curr (thread), curr = curr.left.
  7. * Else: set pred.right = null (restore tree), curr = curr.right.
  8. Step 3: Return result.

Tree Preorder Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Visit Root node (1)
Visual state
Values and pointers at this exact step
tree
Root
1
Left
2
Right
3

Node order shown; add connections to display explicit tree edges.

curr: 1
Check / comparison
Visit current = 1
Decision / next transition
Add 1 to output. Move to left child (2).
Why this step matters

Step 1: Visit Root node (1). Add 1 to result list: [1]. Next explore left child.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> preorderTraversal(TreeNode* root) {
10 vector<int> ans;
11 TreeNode* curr = root;
12 while (curr) {
13 if (!curr->left) {
14 ans.push_back(curr->val);
15 curr = curr->right;
16 } else {
17 TreeNode* pred = curr->left;
18 while (pred->right && pred->right != curr) {
19 pred = pred->right;
20 }
21 if (!pred->right) {
22 ans.push_back(curr->val); // visit before going left
23 pred->right = curr;
24 curr = curr->left;
25 } else {
26 pred->right = nullptr;
27 curr = curr->right;
28 }
29 }
30 }
31 return ans;
32 }
33};
34
35int main() {
36 // Sample driver execution
37 cout << "Execution completed successfully." << endl;
38 return 0;
39}
40

Time & Space Complexity

  • Time complexity: O(n) — Every edge is traversed at most 3 times, guaranteeing linear O(n) total runtime.
  • Space complexity: O(1) — No stack or recursion is used. Only temporary tree pointers, giving O(1) auxiliary space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(n)O(h)Natural call stack recursion: visit, dfs(left), dfs(right).Call stack memory.
2.Iterative StackO(n)O(h)Explicit LIFO stack pushing right child then left child.Explicit stack storage.
3.Morris TraversalOptimalO(n)O(1)Threaded binary tree links from predecessor to current node.None. Space-optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns [].
  • Single node tree: root = [1] -> returns [1].
  • Skewed tree (all left or all right children).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that recursive DFS requires O(h) call stack memory where h is the tree height.
  2. Show how pushing right child before left child into a LIFO stack ensures left is popped first.
  3. Mention Morris Traversal as the follow-up if interviewer asks for O(1) extra space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In the iterative preorder traversal using a stack, why must the right child be pushed before the left child?

Back to DSA Sheet