Binary Tree Preorder Traversal

Difficulty: Easy | Acceptance: 75.70% | Paid: No Topics: Stack, Tree, Depth-First Search, Binary Tree

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

• Examples
• Constraints
• Recursive Approach
• Iterative Approach with Stack
• Morris Traversal

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 4

Input:

root = [1]

Output:

[1]

Constraints

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

Recursive Approach

Intuition Preorder traversal visits nodes in the order: root, left subtree, right subtree. We can naturally implement this using recursion.

Steps

• If the current node is null, return
• Add the current node’s value to the result
• Recursively traverse the left subtree
• Recursively traverse the right subtree

# 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]:
        result = []
        
        def preorder(node):
            if not node:
                return
            result.append(node.val)
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return result

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(h) where h is the height of the tree (recursion stack)
• Notes: Simple and intuitive, but uses recursion stack space

Iterative Approach with Stack

Intuition We can simulate the recursive approach using an explicit stack. The key insight is to push right child first, then left child, so that left is processed first (LIFO).

Steps

• Initialize an empty stack and result list
• Push the root node onto the stack
• While the stack is not empty:
  • Pop a node from the stack
  • Add its value to the result
  • Push right child (if exists) to stack
  • Push left child (if exists) to stack

# 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]:
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        
        return result

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(h) where h is the height of the tree (stack space)
• Notes: Avoids recursion, useful when recursion depth could cause stack overflow

Morris Traversal

Intuition Morris traversal achieves O(1) extra space by temporarily modifying the tree structure. We create temporary links from the rightmost node of the left subtree back to the current node.

Steps

• Initialize current pointer to root
• While current is not null:
  • If current has no left child:
    • Add current’s value to result
    • Move to right child
  • Else:
    • Find the rightmost node in current’s left subtree
    • If rightmost node’s right is null:
      • Add current’s value to result
      • Link rightmost’s right to current
      • Move to left child
    • Else (rightmost’s right points to current):
      • Remove the temporary link
      • Move to right child

# 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]:
        result = []
        current = root
        
        while current:
            if not current.left:
                result.append(current.val)
                current = current.right
            else:
                # Find the rightmost node in left subtree
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right
                
                if not predecessor.right:
                    # Create temporary link
                    result.append(current.val)
                    predecessor.right = current
                    current = current.left
                else:
                    # Remove temporary link
                    predecessor.right = None
                    current = current.right
        
        return result

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(1) extra space (modifies tree temporarily)
• Notes: Most space-efficient but modifies tree structure during traversal