Scribd
Upload
88 views28 pages

Breadth-First Search Guide

The document discusses the breadth-first traversal algorithm for binary trees. It provides pseudocode that places the root node in a queue and dequeues nodes, visiting them and adding children to the queue, until the queue is empty. This results in nodes being visited level-by-level from left to right. Examples are shown of running the algorithm on a sample tree. The time complexity is O(n) as each node is handled twice, and the space complexity is O(n) to store nodes in the queue.

Uploaded by

Joe Manley
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
88 views28 pages

Breadth-First Search Guide

The document discusses the breadth-first traversal algorithm for binary trees. It provides pseudocode that places the root node in a queue and dequeues nodes, visiting them and adding children to the queue, until the queue is empty. This results in nodes being visited level-by-level from left to right. Examples are shown of running the algorithm on a sample tree. The time complexity is O(n) as each node is handled twice, and the space complexity is O(n) to store nodes in the queue.

Uploaded by

Joe Manley
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Alyce Brady

CS 470: Data Structures


CS 510: Computer Algorithms
Breadth-First
Binary Tree
Traversal Algorithm
Reminder:
Breadth-First Traversal

A
B C
D E F G
A B C D E F G
Pseudo-Code for
Breadth-First Traversal
breadth-first-traversal
put root node onto a queue
while the queue is not empty
dequeue the next node
visit the node e.g., print value
enqueue the left child node
enqueue the right child node
Breadth-First Search

A
B C
D E F G
A B C D E F G
Queue:
Current:
Breadth-First Search

A
B C
D E F G
Queue:
Current:
A
Breadth-First Search

A
B C
D E F G
Queue:
Current:
A
A
Breadth-First Search

A
B C
D E F G
Queue:
Current:
A
A
Breadth-First Search

A
B C
D E F G
Queue:
Current:
B
A
A
Breadth-First Search

A
B C
D E F G
Queue:
Current:
C
B
A
A
Breadth-First Search

A
B C
D E F G
Queue:
Current:
B
A
C
B
Breadth-First Search

A
B C
D E F G
Queue:
Current:
B
C
A B
Breadth-First Search

A
B C
D E F G
Queue:
Current:
D
C
B
A B
Breadth-First Search

A
B C
D E F G
Queue:
Current:
E
D
C
B
A B
Breadth-First Search

A
B C
D E F G
Queue:
Current:
C
E
D
C
A B
Breadth-First Search

A
B C
D E F G
Queue:
Current:
C
A B C
E
D
Breadth-First Search

A
B C
D E F G
Queue:
Current:
C
A B C
F
E
D
Breadth-First Search

A
B C
D E F G
Queue:
Current:
C
A B C
G
F
E
D
Breadth-First Search

A
B C
D E F G
Queue:
Current:
D
A B C
G
F
E
D
A B C D
Breadth-First Search

A
B C
D E F G
Queue:
Current:
D
G
F
E
Breadth-First Search

A
B C
D E F G
A B C D
Queue:
Current:
E
G
F
E
Breadth-First Search

A
B C
D E F G
Queue:
Current:
E
G
F
A B C D E
Breadth-First Search

A
B C
D E F G
Queue:
Current:
F
G
F
A B C D E
Breadth-First Search

A
B C
D E F G
Queue:
Current:
F
G
A B C D E F
Breadth-First Search

A
B C
D E F G
Queue:
Current:
G
G
A B C D E F
Breadth-First Search

A
B C
D E F G
Queue:
Current:
G
A B C D E F G
Breadth-First Search

A
B C
D E F G
A B C D E F G
Time and Space Complexity
for Breadth-First Search Alg.
Time Complexity
Consider each node twice O(n)
when put on queue
when taken from queue
Space Complexity
Queue to handle unexplored nodes
Queue length = width of lowest level (n/2)
O(n)
Time and Space Complexity
for Breadth-First Search Alg.

You might also like