#144

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Tree Preorder Traversal

Perform a binary tree preorder traversal by visiting root nodes first, then left and right subtrees, tracking state iteratively or recursively.

stack tree depth first search binary tree

Problem Statement

Given a binary tree, implement a function that returns an array of its node values following a preorder traversal sequence: root first, then left subtree, and finally right subtree. The tree may be empty, and nodes contain integer values in the range [-100, 100].

For example, given root = [1,null,2,3], the output should be [1,2,3], and for root = [1,2,3,4,5,null,8,null,null,6,7,9], the output should be [1,2,4,5,6,7,3,8,9]. Handle trees with up to 100 nodes and ensure the traversal respects the preorder pattern.

Examples

Example 1

Input: root = [1,null,2,3]

Output: [1,2,3]

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]

Example 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Recursive Preorder Traversal

Define a helper function that processes the current node, appends its value to a result list, then recursively calls itself on the left and right children. This approach directly models the preorder pattern but may use O(h) call stack space, where h is the tree height.

Iterative Traversal Using a Stack

Initialize a stack with the root node and iterate while the stack is not empty. Pop the top node, append its value, then push its right child followed by its left child. This ensures the left subtree is processed before the right, maintaining the preorder order while avoiding recursion.

Tracking Null and Leaf Nodes Carefully

Explicitly check for null nodes before pushing them onto the stack to prevent errors. For leaf nodes, ensure they are appended immediately and do not attempt further traversal. Proper state tracking prevents missing nodes or violating the preorder sequence.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once. Space complexity is O(h) for recursion or O(n) for the stack in the worst case, where n is the number of nodes and h is the tree height.

What Interviewers Usually Probe

Looking for correct preorder sequence adherence and null handling.
Checking if candidate differentiates between recursion and iterative stack approaches.
Assessing ability to track traversal state without missing leaf nodes.

Common Pitfalls or Variants

Common pitfalls

Pushing left child after right child incorrectly, reversing preorder order.
Forgetting to check for null nodes, causing runtime errors.
Assuming all trees are complete and not handling sparse trees properly.

Follow-up variants

Inorder and postorder traversal with similar state-tracking logic.
Binary tree with additional constraints, such as skipping certain values.
Traversals returning node objects instead of values for processing.

FAQ

What is the easiest way to implement Binary Tree Preorder Traversal?

Use recursion for simplicity, visiting the root first, then left and right subtrees, or use a stack to iteratively maintain the preorder sequence.

Can this problem be solved iteratively without recursion?

Yes, a stack can simulate the call stack of recursion, ensuring left children are processed before right children.

How do I handle an empty tree in this traversal?

Check if the root is null and return an empty list immediately; GhostInterview highlights this edge case during step-throughs.

What common mistakes occur with stack-based preorder traversal?

Pushing the left child after the right child reverses the expected node order, and forgetting null checks can cause runtime errors.

Why is state tracking important in preorder traversal?

Maintaining accurate traversal state ensures nodes are visited in root-left-right order and prevents skipping or duplicating nodes.

terminal

Solution

Solution 1: Recursive Traversal

We first visit the root node, then recursively traverse the left and right subtrees.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            ans.append(root.val)
            dfs(root.left)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Solution 2: Stack Implementation for Non-Recursive Traversal

The idea of using a stack to implement non-recursive traversal is as follows:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            ans.append(root.val)
            dfs(root.left)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Solution 3: Morris Preorder Traversal

Morris traversal does not require a stack, and its space complexity is $O(1)$. The core idea is:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(root):
            if root is None:
                return
            ans.append(root.val)
            dfs(root.left)
            dfs(root.right)

        ans = []
        dfs(root)
        return ans

Continue Practicing

#145 binary tree postorder traversal #114 flatten binary tree to linked list #94 binary tree inorder traversal