Depth-First Search (DFS) and Depth-First Traversal

0 phút đọc

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.

Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.

Here's a how a DFS would traverse this tree, starting with the root:

A 4-row binary tree represented by circles connected with lines. Our depth-first search has us start at the root node at the top of the tree.

We'd go down the first path we find until we hit a dead end:

The same binary tree with all nodes in the leftmost branch bolded after being visited.

Then we'd do the same thing again—go down a path until we hit a dead end:

Then we do the same thing again: head down the next leftmost path until we reach a dead end.

And again:

And again.

And again:

Until we've visited every node in the tree.

Until we reach the end.

Depth-first search is often compared with breadth-first search.


  • Depth-first search on a binary tree generally requires less memory than breadth-first.
  • Depth-first search can be easily implemented with recursion.


  • A DFS doesn't necessarily find the shortest path to a node, while breadth-first search does.

Bình luận

Chưa có bình luận nào

Chưa có bình luận nào

Avatar TechMely Team
Được viết bởi

TechMely Team

Đôi khi, không cẩn thận biết một số chuyện, mới phát hiện ra rằng những điều bản thân để tâm lại nực cười đến thế.
Khoá học javascript từ cơ bản đến chuyên sâuYoutube Techmely