MRECW Students E- Learning Point Computer Security Student (CSS)

Depth-first

There are three types of depth-first traversal: pre-order, in-order, and post-order For a binary tree, they are defined as display operations recursively at each node, starting with the root node, whose algorithm is as follows:

Pre-order

1. Display the data part of root element (or current element)
2. Traverse the left subtree by recursively calling the pre-order function.
3. Traverse the right subtree by recursively calling the pre-order function.

In-order

1. Traverse the left subtree by recursively calling the in-order function.
2. Display the data part of root element (or current element).
3. Traverse the right subtree by recursively calling the in-order function.

Post-order

1. Traverse the left subtree by recursively calling the post-order function.
2. Traverse the right subtree by recursively calling the post-order function.
3. Display the data part of root element (or current element).

Depth-first search

Order in which the nodes are visited
Class	Search algorithm
Data structure	Graph
Worst case performance	for explicit graphs traversed without repetition, for implicit graphs with branching factor b searched to depth d
Worst case space complexity	if entire graph is traversed without repetition, O(longest path length searched) for implicit graphs without elimination of duplicate nodes