How do you solve Binary Tree Preorder Traversal on LeetCode?

Binary Tree Preorder Traversal (LeetCode #144) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Preorder traversal visits the root before its children.

What is the brute force solution for Binary Tree Preorder Traversal?

The brute force approach for Binary Tree Preorder Traversal is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves recursively traversing the tree and collecting values in preorder. This means we visit the root first, then the left subtree, followed by the right subtree. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Binary Tree Preorder Traversal?

Binary Tree Preorder Traversal uses the following concepts: Stack, Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Stack, Depth-First Search.

What are the interview tips for Binary Tree Preorder Traversal?

Explain your thought process clearly while coding. Consider edge cases, like empty trees or single-node trees. Practice both recursive and iterative solutions.

What are common mistakes when solving Binary Tree Preorder Traversal?

Forgetting to check for null nodes before accessing their children. Not understanding the order of node processing in preorder traversal.

#144

Binary Tree Preorder Traversal

Easy

StackTreeDepth-First SearchBinary TreeStackDepth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses an iterative method with a stack to simulate the recursive behavior of preorder traversal. This avoids the overhead of recursive calls and allows us to control the order of node processing more efficiently.

⚙️

Algorithm

6 steps

1Step 1: Initialize an empty stack and push the root node onto it.
2Step 2: While the stack is not empty, pop the top node.
3Step 3: Add the popped node's value to the result list.
4Step 4: Push the right child of the popped node onto the stack (if it exists).
5Step 5: Push the left child of the popped node onto the stack (if it exists).
6Step 6: Repeat until the stack is empty.

solution.py12 lines

1def preorderTraversal(root):
2    if not root:
3        return []
4    stack, result = [root], []
5    while stack:
6        node = stack.pop()
7        result.append(node.val)
8        if node.right:
9            stack.append(node.right)
10        if node.left:
11            stack.append(node.left)
12    return result

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(n) in the worst case due to the stack storing nodes, especially if the tree is skewed.

1Preorder traversal visits the root before its children.
2Using a stack allows us to simulate recursion iteratively.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.