Binary Tree Breadth-First Search
What is BFS?
Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by level, starting from a source node. It uses a queue data structure to keep track of nodes to visit next.
Key Characteristics
- Level-Order Traversal: Visits all nodes at depth d before visiting nodes at depth d+1
- Queue-Based: Uses FIFO (First-In-First-Out) queue to manage which nodes to visit next
- Complete Algorithm: Guarantees finding a path if one exists
- Optimal for Shortest Path: Finds the shortest path in unweighted graphs
BFS vs DFS
- BFS: Explores breadth-first using a queue. Better for finding shortest paths and analyzing levels.
- DFS: Explores depth-first using a stack or recursion. Better for path finding and topological sorting.
Real-World Applications
- Social Networks: Finding degrees of separation between people
- Web Crawlers: Systematically exploring web pages
- GPS Navigation: Finding shortest routes between locations
- Network Broadcasting: Distributing messages to all nodes
How to Use
- Click Generate New Tree to create a random 15-node binary tree
- Click any node to select it as the starting point (shown with purple fill)
- Click a different node to select it as the target (shown with red border)
- Click Play to watch the BFS algorithm search for the target
- Adjust speed with the dropdown (0.25x - 2x) and use Pause or Reset as needed
- When the target is found, it will turn green and the status will update
- Watch the Status badge to track your progress through the three steps
Visual Guide
- Purple: Starting node
- Red border: Target node (searching)
- Yellow: Currently visiting
- Blue with number: Visited (shows visit order)
- Green: Target found!
- Orange border: Current BFS level
- Generate tree
- Select start node
- Select target node
- Find target node
Tree View
Queue State
Statistics
Progress
-
Current Level
-
Nodes Visited
-
Queue Size
-