Tree - Depth-First Search (DFS)

Data System Architecture

About

Depth-First Search is a tree traversal in a depth-frist order. ie The search tree is deepened as much as possible on each child before going to the next sibling.

Algorithm

At node N, in any order:

  • (L) Recursively traverse its left subtree. When this step is finished you are back at N again.
  • (R) Recursively traverse its right subtree. When this step is finished you are back at N again.
  • (N) Process N itself.
Traversal Type Condition
left-to-right If (L) is done before (R)
right-to-left If (R) is done before (L)

Left-To-Right Algorithm

The order prefix (ie pre in pre-order) refers to the display position of the root or current node.

Order display the root or current node (…) the left or right branch of the tree
pre-order before
in-order between (only for binary tree)
post-order after

Example

h
        /  |  \
      /    |   \
    d      e    g
   /|\          |
  / | \         f
 a  b  c

  • pre-order (hdabcegf),
  • post-order (abcdefgh)

Documentation / Reference





Discover More
Card Puncher Data Processing
Antlr - Parse Tree Visitor

The in Antlr that will visit the parse tree in a depth-first search order In a visitor, you can: control the order of visite return data from the function Use mainly when the code is spread around...
Data System Architecture
Tree - Order

The term tree order describes how a tree is traversed. It can also be a graph data structures, selecting an arbitrary node as the root. The traversals are classified by the order in which the nodes...



Share this page:
Follow us:
Task Runner