🌳 Understanding Depth First Search (DFS) — Inorder Traversal

Back to: Python Data Structure and Algorithims

🌳 Understanding Depth First Search (DFS) — Inorder Traversal

In the world of trees, traversal means visiting every node in a specific order.
When we talk about Depth First Search (DFS), we explore a branch as deeply as possible before backtracking.

In our earlier discussions, we explored two types of DFS:

Preorder traversal — Visit → Left → Right
Postorder traversal — Left → Right → Visit

Now, let’s move to the third and final DFS method — Inorder Traversal.

🧩 What is Inorder Traversal?

In Inorder traversal, the order of visiting nodes is:

👉 Left → Visit → Right

This means:

First, visit the left subtree.
Then, process the current node.
Finally, visit the right subtree.

This approach is especially useful for binary search trees (BSTs) because it naturally visits the nodes in ascending order of their values.

🌿 Example Tree

Let’s take the following binary tree:

Now, we’ll perform Inorder Traversal step by step.

🔍 Step-by-Step Walkthrough

Start at the root (47).
First, we go left to visit 21.
From 21, go left again to visit 18.
- 18 tries to go left — no node.
- So, we write 18 to our results list.
- Then, it tries to go right — no node again.
✅ Results: [18]
Now, we go back up to 21.
- We’ve already gone left, so we now write 21.
- Then, go right to 27.
At 27:
- Go left — nothing there.
- Write 27.
- Go right — nothing there.
✅ Results: [18, 21, 27]
Now, go back up to 47 (the root).
- Left side is complete.
- Write 47.
- Then go right to 76.
At 76:
- Go left to 52.
  - Go left — nothing there.
  - Write 52.
  - Go right — nothing there.
✅ Results: [18, 21, 27, 47, 52]
Back to 76:
- Left is done, so write 76.
- Then go right to 82.
At 82:
- Go left — nothing there.
- Write 82.
- Go right — nothing there.
✅ Final Results: [18, 21, 27, 47, 52, 76, 82]

💡 What Do You Notice?

The Inorder traversal gives us the nodes in sorted (ascending) order.
That’s why this method is so important in Binary Search Trees (BSTs) — it reflects their inherent structure.

🧠 Comparison Recap

Traversal Type	Order	Output (for our example)
Preorder	Visit → Left → Right	[47, 21, 18, 27, 76, 52, 82]
Postorder	Left → Right → Visit	[18, 27, 21, 52, 82, 76, 47]
Inorder	Left → Visit → Right	[18, 21, 27, 47, 52, 76, 82]

💻 Inorder Traversal (Python Example)

Here’s a simple implementation:

class Node:

def __init__(self, value):

self.value = value

self.left = None

self.right = None

def dfs_inorder(root):

result = []

def traverse(node):

if node is None:

return

traverse(node.left) # Visit left

result.append(node.value) # Process current node

traverse(node.right) # Visit right

traverse(root)

return result

# Example Tree

root = Node(47)

root.left = Node(21)

root.right = Node(76)

root.left.left = Node(18)

root.left.right = Node(27)

root.right.left = Node(52)

root.right.right = Node(82)

print(dfs_inorder(root))

Output:

🌟 Final Thoughts

Inorder traversal is a fundamental tree traversal technique.
It’s elegant, recursive, and perfectly suited for retrieving sorted data from binary search trees.

Next time you work with a BST, remember — an Inorder traversal is your key to unlocking sorted order, straight from the tree itself!