# Tree - Depth-First Search (DFS)

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.

## 3 - 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)

## 4 - 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

## 5 - Example

           h
/  |  \
/    |   \
d      e    g
/|\          |
/ | \         f
a  b  c
• pre-order (hdabcegf),
• post-order (abcdefgh)