Tree - Depth-First Search (DFS)
Table of Contents
1 - About
2 - Articles Related
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.
|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-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|
|in-order||between (only for binary tree)|
5 - Example
h / | \ / | \ d e g /|\ | / | \ f a b c
- pre-order (hdabcegf),
- post-order (abcdefgh)