Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the root of a binary tree, return the preorder traversal of its nodes’ values. In preorder traversal, we visit nodes in the following order: root -> left subtree -> right subtree.
Input:
- Root of a binary tree
Output:
- List of integers representing the preorder traversal
Constraints:
- The number of nodes in the tree is in the range [0, 100]
- -100 ≤ Node.val ≤ 100
Examples:
Example 1:
1
\
2
/
3
Input: root = [1,null,2,3,null,null,null]
Output: [1,2,3]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Example 4:
1
/ \
2 3
/ \
4 5
Input: root = [1,2,3,4,5]
Output: [1,2,4,5,3]
Explanation: Visit root(1), then left subtree(2,4,5), then right subtree(3)
Solutions
Approach 1: Recursive Solution
The most intuitive approach using recursion following the natural definition of preorder traversal.
Algorithm:
- Visit the root node (add to result)
- Recursively traverse the left subtree
- Recursively traverse the right subtree
Python:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root):
"""
Recursive preorder traversal
Time: O(N) where N is number of nodes
Space: O(H) where H is height of tree (recursion stack)
"""
result = []
def dfs(node):
if not node:
return
result.append(node.val) # Visit root
dfs(node.left) # Traverse left subtree
dfs(node.right) # Traverse right subtree
dfs(root)
return result
def preorderTraversalCompact(root):
"""
Compact recursive solution
Time: O(N)
Space: O(H)
"""
if not root:
return []
return ([root.val] +
preorderTraversalCompact(root.left) +
preorderTraversalCompact(root.right))
Java:
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
/**
* Recursive preorder traversal
* Time: O(N)
* Space: O(H)
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
dfs(root, result);
return result;
}
private void dfs(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val); // Visit root
dfs(node.left, result); // Traverse left subtree
dfs(node.right, result); // Traverse right subtree
}
/**
* Compact recursive solution
* Time: O(N)
* Space: O(H)
*/
public List<Integer> preorderTraversalCompact(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
result.add(root.val);
result.addAll(preorderTraversalCompact(root.left));
result.addAll(preorderTraversalCompact(root.right));
return result;
}
}
Go:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// preorderTraversal - Recursive preorder traversal
// Time: O(N)
// Space: O(H)
func preorderTraversal(root *TreeNode) []int {
result := []int{}
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
result = append(result, node.Val) // Visit root
dfs(node.Left) // Traverse left subtree
dfs(node.Right) // Traverse right subtree
}
dfs(root)
return result
}
// preorderTraversalCompact - Compact recursive solution
// Time: O(N)
// Space: O(H)
func preorderTraversalCompact(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := []int{root.Val}
result = append(result, preorderTraversalCompact(root.Left)...)
result = append(result, preorderTraversalCompact(root.Right)...)
return result
}
JavaScript:
class TreeNode {
constructor(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
}
/**
* Recursive preorder traversal
* Time: O(N)
* Space: O(H)
*/
function preorderTraversal(root) {
const result = [];
function dfs(node) {
if (!node) {
return;
}
result.push(node.val); // Visit root
dfs(node.left); // Traverse left subtree
dfs(node.right); // Traverse right subtree
}
dfs(root);
return result;
}
/**
* Compact recursive solution
* Time: O(N)
* Space: O(H)
*/
function preorderTraversalCompact(root) {
if (!root) {
return [];
}
return [root.val,
...preorderTraversalCompact(root.left),
...preorderTraversalCompact(root.right)];
}
C#:
using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
/// <summary>
/// Recursive preorder traversal
/// Time: O(N)
/// Space: O(H)
/// </summary>
public IList<int> PreorderTraversal(TreeNode root) {
List<int> result = new List<int>();
Dfs(root, result);
return result;
}
private void Dfs(TreeNode node, List<int> result) {
if (node == null) {
return;
}
result.Add(node.val); // Visit root
Dfs(node.left, result); // Traverse left subtree
Dfs(node.right, result); // Traverse right subtree
}
/// <summary>
/// Compact recursive solution
/// Time: O(N)
/// Space: O(H)
/// </summary>
public IList<int> PreorderTraversalCompact(TreeNode root) {
List<int> result = new List<int>();
if (root == null) {
return result;
}
result.Add(root.val);
result.AddRange(PreorderTraversalCompact(root.left));
result.AddRange(PreorderTraversalCompact(root.right));
return result;
}
}
Approach 2: Iterative Solution using Stack
Use an explicit stack to simulate the recursion call stack.
Algorithm:
- Use a stack to track nodes to be processed
- Push root onto stack
- While stack is not empty:
- Pop node from stack
- Add node’s value to result
- Push right child first, then left child (so left is processed first)
Python:
def preorderTraversalIterative(root):
"""
Iterative preorder traversal using stack
Time: O(N)
Space: O(H)
"""
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val)
# Push right first so left is processed first
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
def preorderTraversalIterativeV2(root):
"""
Alternative iterative approach
Time: O(N)
Space: O(H)
"""
result = []
stack = []
current = root
while stack or current:
if current:
result.append(current.val) # Visit node
if current.right: # Save right child for later
stack.append(current.right)
current = current.left # Go to left child
else:
current = stack.pop() # Process saved right child
return result
Java:
public List<Integer> preorderTraversalIterative(TreeNode root) {
/**
* Iterative preorder traversal using stack
* Time: O(N)
* Space: O(H)
*/
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
// Push right first so left is processed first
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
public List<Integer> preorderTraversalIterativeV2(TreeNode root) {
/**
* Alternative iterative approach
* Time: O(N)
* Space: O(H)
*/
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (!stack.isEmpty() || current != null) {
if (current != null) {
result.add(current.val); // Visit node
if (current.right != null) { // Save right child for later
stack.push(current.right);
}
current = current.left; // Go to left child
} else {
current = stack.pop(); // Process saved right child
}
}
return result;
}
Go:
// preorderTraversalIterative - Iterative preorder traversal using stack
// Time: O(N)
// Space: O(H)
func preorderTraversalIterative(root *TreeNode) []int {
if root == nil {
return []int{}
}
result := []int{}
stack := []*TreeNode{root}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, node.Val)
// Push right first so left is processed first
if node.Right != nil {
stack = append(stack, node.Right)
}
if node.Left != nil {
stack = append(stack, node.Left)
}
}
return result
}
// preorderTraversalIterativeV2 - Alternative iterative approach
// Time: O(N)
// Space: O(H)
func preorderTraversalIterativeV2(root *TreeNode) []int {
result := []int{}
stack := []*TreeNode{}
current := root
for len(stack) > 0 || current != nil {
if current != nil {
result = append(result, current.Val) // Visit node
if current.Right != nil { // Save right child for later
stack = append(stack, current.Right)
}
current = current.Left // Go to left child
} else {
current = stack[len(stack)-1] // Process saved right child
stack = stack[:len(stack)-1]
}
}
return result
}
JavaScript:
/**
* Iterative preorder traversal using stack
* Time: O(N)
* Space: O(H)
*/
function preorderTraversalIterative(root) {
if (!root) {
return [];
}
const result = [];
const stack = [root];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// Push right first so left is processed first
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return result;
}
/**
* Alternative iterative approach
* Time: O(N)
* Space: O(H)
*/
function preorderTraversalIterativeV2(root) {
const result = [];
const stack = [];
let current = root;
while (stack.length > 0 || current) {
if (current) {
result.push(current.val); // Visit node
if (current.right) { // Save right child for later
stack.push(current.right);
}
current = current.left; // Go to left child
} else {
current = stack.pop(); // Process saved right child
}
}
return result;
}
C#:
public IList<int> PreorderTraversalIterative(TreeNode root) {
/// <summary>
/// Iterative preorder traversal using stack
/// Time: O(N)
/// Space: O(H)
/// </summary>
List<int> result = new List<int>();
if (root == null) {
return result;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
result.Add(node.val);
// Push right first so left is processed first
if (node.right != null) {
stack.Push(node.right);
}
if (node.left != null) {
stack.Push(node.left);
}
}
return result;
}
public IList<int> PreorderTraversalIterativeV2(TreeNode root) {
/// <summary>
/// Alternative iterative approach
/// Time: O(N)
/// Space: O(H)
/// </summary>
List<int> result = new List<int>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (stack.Count > 0 || current != null) {
if (current != null) {
result.Add(current.val); // Visit node
if (current.right != null) { // Save right child for later
stack.Push(current.right);
}
current = current.left; // Go to left child
} else {
current = stack.Pop(); // Process saved right child
}
}
return result;
}
Approach 3: Morris Traversal (Space Optimized)
Use Morris traversal to achieve O(1) space complexity by creating temporary links.
Python:
def preorderTraversalMorris(root):
"""
Morris preorder traversal with O(1) space
Time: O(N)
Space: O(1)
"""
result = []
current = root
while current:
if not current.left:
# No left child, visit and go right
result.append(current.val)
current = current.right
else:
# Find inorder predecessor
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
# First time visiting, create link and visit current
result.append(current.val)
predecessor.right = current
current = current.left
else:
# Second time visiting, remove link and go right
predecessor.right = None
current = current.right
return result
Java:
public List<Integer> preorderTraversalMorris(TreeNode root) {
/**
* Morris preorder traversal with O(1) space
* Time: O(N)
* Space: O(1)
*/
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// No left child, visit and go right
result.add(current.val);
current = current.right;
} else {
// Find inorder predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// First time visiting, create link and visit current
result.add(current.val);
predecessor.right = current;
current = current.left;
} else {
// Second time visiting, remove link and go right
predecessor.right = null;
current = current.right;
}
}
}
return result;
}
Go:
// preorderTraversalMorris - Morris preorder traversal with O(1) space
// Time: O(N)
// Space: O(1)
func preorderTraversalMorris(root *TreeNode) []int {
result := []int{}
current := root
for current != nil {
if current.Left == nil {
// No left child, visit and go right
result = append(result, current.Val)
current = current.Right
} else {
// Find inorder predecessor
predecessor := current.Left
for predecessor.Right != nil && predecessor.Right != current {
predecessor = predecessor.Right
}
if predecessor.Right == nil {
// First time visiting, create link and visit current
result = append(result, current.Val)
predecessor.Right = current
current = current.Left
} else {
// Second time visiting, remove link and go right
predecessor.Right = nil
current = current.Right
}
}
}
return result
}
JavaScript:
/**
* Morris preorder traversal with O(1) space
* Time: O(N)
* Space: O(1)
*/
function preorderTraversalMorris(root) {
const result = [];
let current = root;
while (current) {
if (!current.left) {
// No left child, visit and go right
result.push(current.val);
current = current.right;
} else {
// Find inorder predecessor
let predecessor = current.left;
while (predecessor.right && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (!predecessor.right) {
// First time visiting, create link and visit current
result.push(current.val);
predecessor.right = current;
current = current.left;
} else {
// Second time visiting, remove link and go right
predecessor.right = null;
current = current.right;
}
}
}
return result;
}
C#:
public IList<int> PreorderTraversalMorris(TreeNode root) {
/// <summary>
/// Morris preorder traversal with O(1) space
/// Time: O(N)
/// Space: O(1)
/// </summary>
List<int> result = new List<int>();
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// No left child, visit and go right
result.Add(current.val);
current = current.right;
} else {
// Find inorder predecessor
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// First time visiting, create link and visit current
result.Add(current.val);
predecessor.right = current;
current = current.left;
} else {
// Second time visiting, remove link and go right
predecessor.right = null;
current = current.right;
}
}
}
return result;
}
Key Insights
- Visit Order: Preorder visits root before children (Root → Left → Right)
- Stack Simulation: Iterative approach uses stack to simulate recursion
- Right-Left Push Order: Push right child before left to process left first
- Morris Optimization: Can achieve O(1) space using temporary threading
Edge Cases
- Empty tree: Return empty list
- Single node: Return list with one element
- Left skewed tree: Stack/recursion depth equals number of nodes
- Right skewed tree: Minimal stack usage
- Balanced tree: Optimal performance for all approaches
Common Mistakes
- Wrong visit order: Visiting children before root
- Stack push order: Pushing left before right in iterative approach
- Morris implementation: Not properly handling predecessor links
- Base case: Not handling null nodes properly
- Memory modification: Forgetting to restore tree structure in Morris
Follow-up Questions
- Inorder and Postorder: Implement other traversal orders
- Iterative with single stack: Can you do it without the right-first push trick?
- Print vs Return: Modify to print instead of returning values
- Reconstruction: Can you reconstruct tree from preorder and inorder?
- Nth node: Find the nth node in preorder without storing all values