🌳 Coding Depth First Search (DFS) — Inorder Traversal Explained

Back to: Python Data Structure and Algorithims

Coding Depth First Search (DFS) — Inorder Traversal Explained

In the previous post, we explored what Inorder Traversal means conceptually —
a method of visiting a binary tree’s nodes in the order: Left → Visit → Right.

Now, it’s time to bring that theory to life through code!
Let’s walk step-by-step through how the algorithm works internally — using our call stack and our binary tree.

🌿 Our Example Binary Tree

Here’s the same tree we’ve been using throughout this series:

We’ll perform Inorder DFS traversal on this tree.
That means:

Go left as far as possible,
Write the value of the current node,
Then go right.

🧠 Step 1: Writing the Method

We’ll start by defining a method named dfs_inorder().
It will create an empty list called results to hold our output.

Just like in Preorder and Postorder traversals,
we’ll define a nested helper function called traverse(node) that handles recursion.

The only difference between the three DFS types is the order of operations:

Traversal Type	Order
Preorder	Visit → Left → Right
Postorder	Left → Right → Visit
Inorder	Left → Visit → Right

So, for Inorder, we’ll go left, then write, then right.

💻 Step 2: Python Code

Here’s the implementation:

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def dfs_inorder(root):

results = []

def traverse(node):

if not node:

return

# Step 1: Go left

traverse(node.left)

# Step 2: Visit current node

results.append(node.value)

# Step 3: Go right

traverse(node.right)

traverse(root)

return results

Step 3: Understanding the Call Stack Flow

Let’s visualize what happens when we call dfs_inorder(root) on our tree.

We start with 47 (root)
- The algorithm says: Go left first!
- So we move to 21, adding it to the call stack.
At 21
- Again, Go left first!
- We move to 18, pushing it onto the stack.
At 18
- Tries to go left — there’s nothing.
- So, it writes its value 18 to the results list.
- Then it tries to go right — nothing there either.
- Done! ✅
- Pop 18 from the call stack.
📋 results = [18]
Back at 21
- Left subtree done.
- Write 21 to the list.
- Then move right to 27.
📋 results = [18, 21]
At 27
- Left is empty.
- Write 27.
- Right is empty.
- Done! Pop 27.
📋 results = [18, 21, 27]
Back to 47
- Left side (21 subtree) done.
- Write 47.
- Then move to the right → 76.
📋 results = [18, 21, 27, 47]
At 76
- Go left to 52.
- 52 has no left, so write 52.
- No right either, so pop it.
📋 results = [18, 21, 27, 47, 52]
Back at 76
- Left done.
- Write 76.
- Go right → 82.
📋 results = [18, 21, 27, 47, 52, 76]
At 82
- Left is empty.
- Write 82.
- Right is empty.
📋 results = [18, 21, 27, 47, 52, 76, 82]

🧩 Step 4: The Final Result

When we’re done, the traversal has visited every node —
and the values appear in sorted (ascending) order:

This is no coincidence —
Inorder traversal naturally sorts the data in a Binary Search Tree (BST).

🧪 Step 5: Full Example in VS Code

Here’s the complete runnable example:

Output:

🌟 Conclusion

Inorder traversal is a beautiful demonstration of recursion and order.
It explores each branch thoroughly, and when applied to a Binary Search Tree,
it gives us sorted data automatically — no extra sorting needed!

So far, we’ve seen:

Preorder traversal — great for copying a tree.
Postorder traversal — great for deleting a tree.
Inorder traversal — perfect for retrieving sorted values.