# Tree Traversal: Breadth-First Search and Depth-First Search

Learn about two different methods of tree traversal.

Start## Key Concepts

Review core concepts you need to learn to master this subject

Depth-First Search Complexity

DFS Implementations

Depth-First Search Algorithm

Depth-First Search and Stacks

Depth-First Search Complexity

Depth-First Search Complexity

DFS has time and space complexity of `O(n)`

.

Breadth-First Search: Python

Lesson 1 of 2

- 1The breadth-first search is a tree traversal algorithm that searches a tree level by level. The search starts with the root node and works its way through every sibling node on a level before movin…
- 2There are many real-world examples that can be represented by the tree data structure. For example, locations on a map can be represented by a tree, where the children of a location node are locati…
- 3Initializing the search function is the first step to the main algorithm. The parameter of the function should include the following two pieces of data needed to perform the search: - the root nod…
- 4With the function created, we will now start the algorithm by initializing the frontier queue. In this implementation, the frontier queue is called path_queue and will hold a list for each node tha…
- 5The heart of the algorithm is the loop that contains the search process. The first half of this process is: Pop the next path list off the frontier Get the frontier node from the path list Check if…
- 6Now on to the second half of the search process: For each child of the current node Make a copy of the current path Add the child to the copy Append the updated path to the frontier To ens…

## How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory