1
$\begingroup$

The standard implementation of breadth-first search looks like

queue = [root]
while queue:
    node = queue.pop()
    visit(node)
    for_each child in node.children:
        queue.push(child)

Just by switching the queue to a stack:

stack = [root]
while stack:
    node = stack.pop()
    visit(node)
    for_each child in node.children:
        stack.push(child)

we get depth-first search.

There is another way to write breadth-first search:

visit(root)
queue = [root]
while queue:
    node = queue.pop()
    for_each child in node.children:
        visit(child)
        queue.push(child)

But when you switch this one from a queue to a stack:

visit(root)
stack = [root]
while stack:
    node = stack.pop()
    for_each child in node.children:
        visit(child)
        stack.push(child)

You do not get a traditional depth-first search. Instead, you get a variant where all a node's immediate children are visited first, then its other ancestors in a depth-first way. For example, on this tree:

     F
   /   \
  B     G
 / \     \
A   D     I
   / \   /
  C   E H

Depth-first search gives the order

[F, G, I, H, B, D, E, C, A]

The last algorithm gives the order

[F, B, G, I, H, A, D, C, E]

which is not exactly depth-first because B and G are both visited before I. Does this algorithm have a name?

$\endgroup$
  • $\begingroup$ Would you like to give an example where this algorithm is better than other kinds of tree traversal? $\endgroup$ – Apass.Jack Nov 12 '18 at 20:24
  • $\begingroup$ Ok, the infinite loop is fixed, but the visit sequence produced by this code is [a, b, c, e, f, i, j, h, d, g], not [a, b, c, d, g, e, f, h, i, j]. Right now, as reinierpost says, it is a depth-first search with preorder, however with the minor variation that you mark a node $v$ visited as soon as you see it in the list of children of its parent, and not when you pop $v$ (which is more usual). If you instead call visit(v) when popping $v$, you get [a, c, f, j, i, e, h, b, d, g] -- a "proper" preorder depth-first search. $\endgroup$ – Vincenzo Nov 13 '18 at 22:39
  • $\begingroup$ @Vincenzo "with the minor variation that you mark a node v visited as soon as you see it in the list of children of its parent, and not when you pop v" Right, exactly. I'm just curious if this has a name in the literature already or not. You're right that I still got the order wrong, I'll fix it up. $\endgroup$ – Tavian Barnes Nov 13 '18 at 22:43
  • $\begingroup$ In for child in node.children, are children iterated from left to right or right to left? $\endgroup$ – Apass.Jack Nov 14 '18 at 1:55
  • $\begingroup$ @Apass.Jack Left to right, but it doesn't particularly matter. $\endgroup$ – Tavian Barnes Nov 14 '18 at 2:00
1
+50
$\begingroup$

Summary: We can name it (a variant of) preorder children-together depth-first traversal. No particular name or usage for this search algorithm has been found in existing literature yet.


The words "search" and "traversal" are often used interchangeably. In strict sense, this is a traversal algorithm but not a search algorithm (binary search algorithm is a proper search algorithm) since it is not actually searching for any element. Any traversal algorithm can be used for searching naturally, though, which is why we see depth-first search and breadth-first search often.

Description of this algorithm

Firstly, it visits a parent before its children and, hence, before all its descendants)

This property can be considered as the naturalness of a tree traversal algorithm since a parent comes before its children conceptually and historically. Or we can reuse the more conventional term, "preorder" to describe it.

Secondly, it visits children together, but not grandchildren together in general.

Given any node, once it starts traversing its children, it will visit all of its children before any of its further descendants such as grandchildren, great-grandchildren, etc. In other words, all children of any given node will be visited consecutively, in some order which can be specified as, for example, from left child to right child (or some random order).

Thirdly, it is mostly depth-first. After visiting any node, it visits all of its descendants together.

Given any node, once this algorithm begins visiting any of its descendants, it will visit all of its descendants before visiting any node that is not its descendant. It goes deeper and deeper down the descendants towards the leaves, until it reaches the leaves, at which time it will backtrack.

Fourthly, it is not the standard depth-first traversal (SDFS).

For any two siblings nodes $s_1$ and $s_2$, if SDFS visits $s_1$ before $s_2$, then it visits all descendants of $s_1$ before all descendant of $s_2$ as well as $s_2$ itself. In others words, for any two disjoint subtrees $t_1$ and $t_2$, SDFS will either visit $t_1$ completely before $t_2$ or visit $t_2$ completely before $t_1$. However, for this traversal algorithm, if it visit $s_1$ before $s_2$, then it will visit all descendants of $s_1$ after it has visited the subtree at $s_2$.

This fourth point is also implied by the second point.

So this algorithm can be called a variant of preorder children-together depth-first traversal.

Why do we say "a variant of"?

The following algorithm is the algorithm that should be called the preorder children-together depth-first traversal, as it is more natural in the sense that all immediate or distant siblings are visited from left to right, in the same order as children of the same node is visited. In other words, all nodes in the same level are visited from left to right, although not consecutively in general.

myStack = [root]  // myStack is a stack.
while myStack:
    node = myStack.pop()
    for child in node.children: // assuming left to right
        visit(node)
    for child in node.children.reverse: // pushing children in reverse order
        myStack.push(child)

The output of above algorithm on the graph in the question is

F B G A D C E I H

Note that nodes in each level is always visited left to right as [F], [B,G], [A,D,I] and [C, E, H]. This algorithm is also more natural in the sense that can be defined recursively naturally as the following pseudocode in Python style

def traversal(tree, node):
   for child in tree.getChildren(node):
     visit(child)
   for child in tree.getChildren(node):
     traversal(tree, child)

To traverse a tree T rooted at R, call it as visit(R); traversal(T, R).


We can generalize this algorithm so that all $k$-level descendants are visited together. For example, we can have a preorder grandchildren-together depth-first traversal, which may output F B G A D I C E H for the given graph. There are several variations to them, which will not be discussion here.

Tree or general graph

Please note all search strategies mentioned above and in the question can be adapted slightly so as to be applied to general undirected graphs instead of rooted trees. All we need are the following changes. (More adaptation is needed for general directed graphs.)

  • Select an arbitrary node as the root.
  • Initialize a boolean array to record whether a node has been visited or not.
  • Mark a node as visited right after it has been visited.
  • Skip pushing any visited node to the stack or queue.

Two simple exercises

Exercise 1. Write the algorithm in the question as a recursive function/method in pseudocode or your favorite language.

Exercise 2. Suppose every parent should be visited after all its descendants. Implement that variation in pseudocode or your favorite language. Show its output for the given graph.

$\endgroup$
2
$\begingroup$

I don't think it has any standard name, but you might arguably call it a depth-first search with one level of lookahead.

$\endgroup$
  • $\begingroup$ Sounds nice. However, lookahead implies those nodes may be visited more than once, which is not consistent with the current algorithm where each node is visited once. Also lookahead was used when the input is linear. It become much less certain when the input is a tree or general graph. For example, one can easily (mis)understand it as checking children or grandchildren beforehand. $\endgroup$ – Apass.Jack Nov 19 '18 at 5:30

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.