# Tree - Depth-First Search (DFS)

### Table of Contents

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