Data Structure

Class : B.Sc , BCA I Year 

Topic Name : Binary Tree Traversal

Faculty : Asst Prof Sonika Mourya

Binary tree traversal is the process of visiting each node in the tree exactly once in a systematic way. The primary methods fall into two main categories: Depth-First Search (DFS) and Breadth-First Search (BFS). 

Depth-First Search (DFS) Traversals

DFS explores as far as possible along each branch before backtracking. The three common types are: 

·         In-order Traversal: Visits the left subtree, then the current node, and finally the right subtree. For a binary search tree (BST), this visits nodes in ascending order.

·         Pre-order Traversal: Visits the current node, then the left subtree, and finally the right subtree. This is useful for copying trees or generating prefix expressions.

·         Post-order Traversal: Visits the left subtree, then the right subtree, and finally the current node. This is useful for deleting trees or generating postfix expressions. 

Breadth-First Search (BFS) Traversal

BFS, or Level-order Traversal, visits nodes level by level from left to right. It typically uses a queue. 

Summary Table of Traversal Orders

Traversal Name	Order of Visitation
In-order	Left, Root, Right
Pre-order	Root, Left, Right
Post-order	Left, Right, Root
Level-order	Level by level