DSA Pre-order Traversal
Pre-order traversal visits a node before its children, following a root-left-right pattern that makes it the natural choice for copying trees and building prefix expressions.
What Is Pre-order Traversal?
Pre-order traversal is a depth-first strategy that processes nodes in root, left, right order. At each node you first visit the node itself, then recursively traverse its entire left subtree, and only after that traverse its entire right subtree. Because a parent is always handled before any of its descendants, the resulting sequence mirrors the tree's shape from the top down.
This ordering makes pre-order the go-to traversal whenever a task depends on visiting a parent before its children. It is used to serialize a tree into a flat list that can rebuild the same shape, to copy a tree node by node, and to print expression trees in prefix (Polish) notation, where an operator appears before its operands.
Recursive Pre-order Traversal
Example: Recursive Pre-order
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(node, result=None):
if result is None:
result = []
if node is None:
return result
result.append(node.value)
preorder(node.left, result)
preorder(node.right, result)
return result
# Tree: F is the root; B and G are its left and right children.
# B's children are A and D; D's children are C and E.
# G's right child is I, and I's left child is H.
root = Node('F',
Node('B', Node('A'), Node('D', Node('C'), Node('E'))),
Node('G', None, Node('I', Node('H'))))
print(preorder(root))
# ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']Iterative Pre-order Traversal (Using a Stack)
Recursion works well for pre-order because it reuses the call stack Python already manages, but very deep or lopsided trees can exceed Python's recursion limit. An iterative version replaces the call stack with an explicit one: push the root, then repeatedly pop a node, record its value, and push its right child before its left child so the left child ends up on top and is visited first.
Example: Iterative Pre-order
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder_iterative(root):
if root is None:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.value)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is popped first
return result
root = Node('F',
Node('B', Node('A'), Node('D', Node('C'), Node('E'))),
Node('G', None, Node('I', Node('H'))))
print(preorder_iterative(root))
# ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']Example: Cloning a Tree with Pre-order
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(node, result=None):
if result is None:
result = []
if node is None:
return result
result.append(node.value)
preorder(node.left, result)
preorder(node.right, result)
return result
def clone_tree(node):
if node is None:
return None
new_node = Node(node.value)
new_node.left = clone_tree(node.left)
new_node.right = clone_tree(node.right)
return new_node
root = Node('F', Node('B', Node('A'), Node('D')), Node('G'))
copy_of_root = clone_tree(root)
print(preorder(root)) # ['F', 'B', 'A', 'D', 'G']
print(preorder(copy_of_root)) # ['F', 'B', 'A', 'D', 'G']
print(copy_of_root is root) # False - a separate tree in memory- Visit order is root, then left subtree, then right subtree
- A parent always appears before any of its descendants in the output
- Combined with null markers, it can reconstruct a tree's exact shape
- Matches prefix (Polish) notation for expression trees
- Runs in O(n) time and O(h) extra space, where h is the tree's height
