Pre-order Traversal

Pre-order traversal is a type of tree traversal that follows the "root, left, right" order. This means that for each node, the algorithm first processes the node itself, then recursively traverses the left subtree, and finally recursively traverses the right subtree. It's often used to create a copy of the tree or to get a prefix expression of an expression tree.

Pre-Order Traversal (Tree)

Step 1 of 0

Action

Ready to start

Current Node

None

Call Stack

[]

Traversal Order

[]

Current Node

Visited

In Call Stack

Unvisited

Pre-order Traversal Algorithm

Pre-order traversal is a classic depth-first search (DFS) strategy for trees. The "pre-order" name comes from the fact that the root node is processed *before* its left and right subtrees.

Algorithm Steps (Recursive)

Visit the current node (e.g., add its value to a list).
Recursively call pre-order traversal on the left child, if it exists.
Recursively call pre-order traversal on the right child, if it exists.
The base case for the recursion is when a node is null.

Recursive Pre-order Traversal


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

Iterative Pre-order Traversal

The iterative approach for pre-order traversal uses a stack to explicitly manage the nodes to visit. This avoids deep recursion and potential stack overflow issues.

Algorithm Steps

Initialization: Create an empty stack and push the root node onto it.
Loop: While the stack is not empty, do the following:
Pop a node from the stack and process its value.
Push the right child onto the stack if it exists.
Push the left child onto the stack if it exists. (The left child is pushed last so it's processed first, maintaining the pre-order sequence).

Iterative Pre-order Traversal


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