Back to: Python Data Structure and Algorithims

Understanding Tree Traversal in Data Structures

When working with trees in data structures, one of the most important concepts to understand is tree traversal.

But what exactly does tree traversal mean?

In simple terms, tree traversal means visiting every node in a tree exactly once.
During this process, we often perform an operation — such as collecting the node values in a list, printing them on the screen, or applying some logic at each node.

🔍 Why Tree Traversal Is Important

Unlike a linked list, which is linear (you move from one node to the next in one direction), a tree is a hierarchical structure.
That means each node can have multiple children.

So, while traversing a linked list is as simple as:

head → next → next → next → None

Traversing a tree can be done in multiple ways, depending on the order in which we want to visit the nodes.

🌿 Two Main Types of Tree Traversal

There are two main categories of traversals:

Breadth-First Search (BFS)
Depth-First Search (DFS)

Let’s understand both with examples.

🧩 1. Breadth-First Search (BFS)

In Breadth-First Search, we start at the root node and visit all nodes level by level — from top to bottom, and from left to right within each level.

Example Tree:

BFS Traversal Order:
👉 A → B → C → D → E → F

Explanation:

Start at the top (A)
Visit all nodes in the next row (B and C)
Move to the next row (D, E, and F)

This way, BFS explores the tree level-wise, which is why it’s also known as Level Order Traversal.

🌲 2. Depth-First Search (DFS)

In Depth-First Search, instead of exploring level by level, we go as deep as possible along one branch, then backtrack and explore the rest.

There are three types of DFS traversals depending on the order of visiting nodes:

a) Inorder Traversal (Left → Root → Right)

Example Tree:

Inorder Traversal:
👉 D → B → E → A → C

We first go to the leftmost node, then visit the parent, then the right.

b) Preorder Traversal (Root → Left → Right)

Traversal:
👉 A → B → D → E → C

We visit the root first, then explore the left subtree, and finally the right.

c) Postorder Traversal (Left → Right → Root)

Traversal:
👉 D → E → B → C → A

We visit all child nodes first and then the parent nodes — ideal for deleting or freeing trees.

⚙️ Visualizing the Difference

Imagine reading a family tree:

Breadth-First Search is like reading generation by generation — grandparents first, then parents, then children.
Depth-First Search is like following one family line as deep as possible before coming back to the others.

🧠 Summary

Traversal Type	Order of Visiting	Example Output
BFS (Level Order)	Top to bottom, left to right	A, B, C, D, E, F
Inorder (DFS)	Left → Root → Right	D, B, E, A, C
Preorder (DFS)	Root → Left → Right	A, B, D, E, C
Postorder (DFS)	Left → Right → Root	D, E, B, C, A

💡 Final Thoughts

Tree traversal might sound complex at first, but it’s simply about deciding which node to visit next.
Whether you go wide (BFS) or deep (DFS) depends on the problem you’re solving.

Want to print nodes level by level? → Use BFS
Want to evaluate or delete subtrees? → Use DFS