Introduction to DFS Traversals

Introduction to DFS Traversals

Depth-First Search, or DFS, is a traversal technique that explores one branch of a tree as deeply as possible before backtracking to explore another branch.

In a binary tree, every node can have a left child and a right child. DFS starts from the root and recursively explores these subtrees.

The three fundamental DFS traversals are:

• Preorder: Root → Left → Right

• Inorder: Left → Root → Right

• Postorder: Left → Right → Root

The difference between them is the moment at which the current node is processed.

Consider a binary tree with the following relationships:

• Node 1 is the root.

• Nodes 2 and 3 are the left and right children of 1.

• Nodes 4 and 5 are the children of 2.

• Nodes 6 and 7 are the children of 3.

Its DFS traversal orders are:

How Does DFS Work?

DFS follows the recursive structure of a binary tree.

For every node:

• Process the current node at the required moment.

• Explore its left subtree.

• Explore its right subtree.

• Return to its parent after both required subtrees are complete.

Whenever a NULL node is reached, that branch has ended, so traversal returns to the previous node.

This return to a previous node is called backtracking.

A recursive DFS uses the program’s call stack to remember:

• The current node

• Which subtree is being explored

• Where execution must continue after a recursive call returns

An iterative DFS stores the same information explicitly inside a stack.

The Three-Moment Mental Model

Every node has three important moments during DFS:

1. Entry: The traversal reaches the node before exploring either subtree.

2. Between: The left subtree is complete, but the right subtree has not yet been explored.

3. Exit: Both subtrees are complete, and traversal is about to return to the parent.

These moments directly define the three DFS traversals:

A useful way to remember the orders is to observe where Root appears:

• Preorder: Root comes before both subtrees.

• Inorder: Root comes in between the subtrees.

• Postorder: Root comes after both subtrees.

Recursive DFS Structure

Every recursive DFS traversal follows the same basic structure:

• Stop when the current node is NULL.

• Recursively explore the left subtree.

• Recursively explore the right subtree.

• Process the root before, between, or after these recursive calls.

Only the processing position changes between preorder, inorder, and postorder.

Because every subtree is itself a binary tree, the same procedure can be applied repeatedly until leaf nodes and then NULL references are reached.

1. Preorder Traversal

Preorder follows:

Root → Left → Right

The current node is processed immediately when it is entered.

Example

Using the example tree:

• Visit root 1.

• Traverse the left subtree rooted at 2.

• Visit 2, followed by 4 and 5.

• Traverse the right subtree rooted at 3.

• Visit 3, followed by 6 and 7.

The preorder traversal is:

1, 2, 4, 5, 3, 6, 7

Algorithm

• Check whether the current node is NULL; if so, return because the branch has ended.

• Process the current node before visiting either of its children.

• Recursively traverse the left subtree.

• Recursively traverse the right subtree.

• Return after both subtrees have been processed.

Common Uses

Preorder traversal is useful for:

• Creating a copy of a tree

• Serializing a tree with structural markers

• Generating prefix expressions

• Processing a parent before its children

• Recording root-to-node paths

2. Inorder Traversal

Inorder follows:

Left → Root → Right

The current node is processed after its left subtree but before its right subtree.

Example

Using the example tree:

• Traverse the left subtree of 1.

• Visit 4, then 2, then 5.

• Process root 1.

• Traverse the right subtree.

• Visit 6, then 3, then 7.

The inorder traversal is:

4, 2, 5, 1, 6, 3, 7

Algorithm

• Check whether the current node is NULL; if so, return because the branch has ended.

• Recursively traverse the left subtree.

• Process the current node after the left subtree is complete.

• Recursively traverse the right subtree.

• Return after the right subtree has been processed.

Common Uses

Inorder traversal is useful for:

• Retrieving values of a Binary Search Tree in sorted order

• Processing values between the left and right subtrees

• Generating infix expressions from expression trees

• Finding ordered relationships in a Binary Search Tree

Inorder traversal does not produce sorted values for a general binary tree. The sorted result depends on the ordering property of a Binary Search Tree.

3. Postorder Traversal

Postorder follows:

Left → Right → Root

The current node is processed only after both of its subtrees are complete.

Example

Using the example tree:

• Traverse the left subtree of 1.

• Visit 4 and 5 before processing 2.

• Traverse the right subtree.

• Visit 6 and 7 before processing 3.

• Process root 1 after both complete subtrees.

The postorder traversal is:

4, 5, 2, 6, 7, 3, 1

Algorithm

• Check whether the current node is NULL; if so, return because the branch has ended.

• Recursively traverse the left subtree.

• Recursively traverse the right subtree.

• Process the current node after both subtrees are complete.

• Return to the parent node.

Common Uses

Postorder traversal is useful for:

• Deleting or freeing a tree

• Calculating subtree heights

• Checking whether a tree is balanced

• Calculating tree diameter

• Evaluating expression trees

• Generating postfix expressions

• Solving problems where a parent depends on results from both children

Comparing the Three DFS Traversals

The left subtree is explored before the right subtree in all three standard traversals. Only the processing position of the root changes.

Iterative DFS Using a Stack

Recursion automatically stores unfinished function calls in the call stack. An iterative traversal performs the same work using an explicit stack.

Iterative Preorder

To preserve Root → Left → Right order:

• Push the root into the stack.

• Remove the top node and process it.

• Push its right child before its left child.

• Continue until the stack becomes empty.

The right child is pushed first because a stack follows Last In, First Out order, causing the left child to be processed first.

Iterative Inorder

To preserve Left → Root → Right order:

• Move through left children while storing the visited nodes in a stack.

• When no further left child exists, remove the top node and process it.

• Move to its right child.

• Repeat until both the current node and stack are empty.

Iterative Postorder

Postorder can be implemented using:

• Two stacks

• One stack with previous-node tracking

• One stack with a state value

The state-based method is especially useful because it can also generate preorder, inorder, and postorder together.

Preorder, Inorder, and Postorder in One Traversal

All three traversal orders can be generated during one iterative DFS using a stack of pairs:

(node, state)

The state describes which of the three moments has been reached for that node:

Each node progresses through:

State 1 → State 2 → State 3

State 1: Preorder Event

When a node is removed with state 1:

• Add its value to the preorder result.

• Change its state to 2 and place it back into the stack because it must be revisited after its left subtree.

• If its left child exists, place the left child into the stack with state 1.

This follows:

Root → Left

State 2: Inorder Event

When a node is removed with state 2:

• Add its value to the inorder result.

• Change its state to 3 and place it back into the stack because it must be revisited after its right subtree.

• If its right child exists, place the right child into the stack with state 1.

This occurs between:

Left → Root → Right

State 3: Postorder Event

When a node is removed with state 3:

• Add its value to the postorder result.

• Do not place the node back into the stack because both subtrees are complete.

This completes:

Left → Right → Root

Algorithm

• Create empty preorder, inorder, and postorder result lists.

• If the root is not NULL, place (root, 1) into the stack.

• For state 1, record preorder, return the node with state 2, and begin its left subtree.

• For state 2, record inorder, return the node with state 3, and begin its right subtree.

• For state 3, record postorder because both subtrees are complete.

• Continue until the stack becomes empty, then return all three traversal orders.

Dry Run of All Three Traversals Together

Consider a smaller tree:

• Node 1 is the root.

• Node 2 is its left child.

• Node 3 is its right child.

Initial stack:

[(1, 1)]

Initial results:

Preorder = []

Inorder = []

Postorder = []

Final results:

Preorder = [1, 2, 3]

Inorder = [2, 1, 3]

Postorder = [2, 3, 1]

Complexity Analysis

Complexity of Individual DFS Traversals

Each node is processed once in an individual traversal.

Time Complexity: O(N)

For recursive DFS, the call stack stores nodes along the current path.

Auxiliary Space Complexity: O(H)

where H is the height of the tree.

• Balanced tree: O(log N)

• Skewed tree: O(N)

The output list requires O(N) additional space when the traversal result must be stored.

Complexity of All Three Traversals Together

Each node passes through three constant states.

The total work is:

3 × N

Ignoring the constant factor:

Time Complexity: O(N)

The stack stores nodes along the active traversal path.

Auxiliary Space Complexity: O(H)

The three output lists together contain 3N values, which simplifies to:

Output Space: O(N)

The combined traversal does not improve the asymptotic complexity compared with running three separate traversals. Its advantage is that all three orders are generated through one coordinated stack process.

Recursive and Iterative DFS Comparison

Both methods perform the same logical traversal. The main difference is where the pending work is stored.

How to Choose the Correct DFS Traversal

Use preorder when:

• The parent must be processed before its children.

• A root-first representation is required.

• A path must be built while moving downward.

Use inorder when:

• Values of a Binary Search Tree are required in sorted order.

• Processing must occur between the two subtrees.

• An infix representation is required.

Use postorder when:

• A node depends on information returned by its children.

• Subtrees must be completed before the parent.

• Height, diameter, balance, or subtree properties must be calculated.

Use the combined traversal when:

• All three orders are required.

• A single explicit-stack process is preferred.

• The three node-processing moments need to be demonstrated or recorded.

Common Mistakes

• Forgetting the NULL base case in recursive traversal.

• Processing the node at the wrong position.

• Confusing preorder with inorder or postorder.

• Assuming inorder traversal is sorted for every binary tree.

• Pushing the left child before the right child in iterative preorder, causing the right subtree to be processed first.

• Forgetting to store nodes while moving left in iterative inorder.

• Recording a node in postorder before both subtrees are complete.

• Forgetting to update the state before placing a node back into the combined stack.

• Adding a node to multiple traversal lists during the same state.

• Ignoring the O(N) recursion depth of a skewed tree.

• Including output storage inside auxiliary space without stating the convention.

• Treating 3N work in the combined traversal as a different asymptotic complexity from O(N).