2
$\begingroup$

From my understanding, two separate and distinct operations can be performed on binary search trees: Search and Traversal.

Search: Given a key, search will run an algorithm to find the node containing that key in the tree, then return this node.

Traversal: Using a Breadth-First or Depth-First search algorithm, visit every node in the tree.

The above two operations are distinct and have separate algorithms with little in common.

Considering Breadth-First Search and Depth-First Search perform a traversal operation and not a search operation, why are they commonly called such instead of Depth-First Traversal and Breadth-First Traversal?

I'm curious if there's something I've misunderstood here, or there's a specific reason for this.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ "separate algorithms with little in common": could you please expand on this ? $\endgroup$
    – Yves Daoust
    Apr 15 at 9:57
  • $\begingroup$ Here is the etymology of "depth-first search". A draft of chapter 12a of TAOCP reads "The term depth-first search was introduced by Nils Nilsson in his classic book Problem-Solving Methods in Artificial Intelligence (New York: McGraw–Hill, 1971)." $\endgroup$
    – John L.
    Apr 15 at 16:03
  • $\begingroup$ That book by Nils Nilsson reads, "A depth-first search procedure, often called "backtrack programming" in computer science, is described by Golomb and Baumert (1965)". That article by Golomb and Baumert can be found here. $\endgroup$
    – John L.
    Apr 15 at 16:04

3 Answers 3

Reset to default
3
$\begingroup$

Considering Breadth-First Search and Depth-First Search perform a traversal operation and not a search operation

I would not say that as a blanket statement. While it does make sense in certain context it can be very misleading.

As one who programs in Prolog daily, traversal and search are very distinct.

When I see the word traversal used explaining code I expect the code to visit every node of a structure (think tree, graph, list, etc.). Traversals are typically hidden inside map functions and thus visit every node.

When I see the word search I also think of guards that modify the search and search indexes that make the search more efficient. Also a search may visit all of the nodes, some of the nodes or only one node, a search does not always need to visit every node and often does not.

However there are other types of methods/functions/predicates that use callbacks and will traverse a structure but use the call back to access guards and search indexes making the traversal more efficient.

You noted binary tree but it makes more sense if one uses a binary search tree instead meaning the values are ordered such that for a node all values greater are in the left branch and all lesser values are in the right branch.

A traverse of a binary search tree will visit every node of the tree.

A depth-first search of binary search tree will use the value at the node to decide to search the left or right branch. This obviously does not traverse the entire tree.

A breadth-first search of a binary search tree seems senseless. (confused emoji goes here) It is ignoring the fact that a binary search tree is constructed to quickly find a value by comparing the current value and picking the left or right branch.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for this explanation. One thing I don't get when you say a depth-first search will use the values at nodes to decide the next branch, and also not traverse the entire tree. I thought how it traversed was independent of any value, but rather it always takes the left (or right) most branch until it hits a dead end, then backtracks to a node with an unsearched branch, and repeats this process until the entire tree is traversed? If this isn't the case this might be the source of my confusion $\endgroup$
    – user4779
    Apr 15 at 15:55
  • $\begingroup$ @user4779 Your explanation of traversal is correct. I think you need to realize that the phrases Depth First Search and Depth First Traversal are two different phrases and can easily be confused at first. Depth First Traversal does what you noted and is the same as Depth First Search but just keeps going until the entire structure is done. While Depth First Search will stop when it finds a match or fails. Often to optimize the code the DFS will keep track of where it left off and continue from that point to return the next result if there is one, rinse and repeat as needed. $\endgroup$
    – Guy Coder
    Apr 15 at 16:06
  • 1
    $\begingroup$ This definitely was the source of my confusion. I thought the two terms were interchangeable, not helped by Google showing results for DFS when I enter DFT. Now I can see DFT is an application of DFS with a different purpose. Thank you for clarifying this $\endgroup$
    – user4779
    Apr 15 at 16:13
  • 1
    $\begingroup$ @user4779 When I Googled for an example this was the first hit. I did not even get past the first sentence before it became apparent as to what could be causing your confusion. :) $\endgroup$
    – Guy Coder
    Apr 15 at 16:17
  • $\begingroup$ "A depth-first search of binary search tree will use the value at the node to decide to search the left or right branch" - I very strongly disagree with calling this "depth-first search". What exactly do you think is "depth-first" about that search? "Depth-first" implies that depth is the first thing being searched, which suggests there can be more than one thing (with the second thing being breadth in DFS), but depth is the only thing with a binary search tree lookup. $\endgroup$
    – NotThatGuy
    Apr 15 at 18:19
4
$\begingroup$

It seems that you are only focusing on a very limited use of BFS and DFS.

Consider this wikipedia entry for BFS, where it was stated that BFS was invented to find a connected component and was later rediscovered as an algorithm for finding shortest path out of a maze. This entry on DFS, states that it was use to solve mazes which basically means finding a path.

What I simply mean from above is that both algorithms are really meant for searching, although different from how you search using a BST. Based on the articles, BFS (1945/1959) and DFS (19th Century) predates the invention of BST (1960). Using BFS and DFS as traversal strategy is just an application of these algorithms.

Improve this answer
$\endgroup$
0
$\begingroup$

Traversal means visiting every element exactly once but in case of DFS , elements are visited more than once , that's why it is known as searching rather than traversal .

Improve this answer
$\endgroup$
1
  • $\begingroup$ Depth-first search is considered a type of tree traversal here on Wikipedia. $\endgroup$
    – John L.
    Apr 22 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.