| Tree |
Pre-order Traversal |
1. Inspect node [Pre-Order(node)]2. Traverse left sub-tree [Pre-Order(node->left)].3. Traverse right sub-tree [Pre-order(node->right)] |
Stack |
O(N) |
| Tree |
In-order Traversal |
1. Traverse left sub-tree [In-Order(node->left)]2. Inspect node [In-Order(node)].3. Traverse right sub-tree [In-order(node->right)] |
Stack |
O(N) |
| Tree |
Post-order Traversal |
1. Traverse left sub-tree [Post-Order(node->left)]2. Traverse right sub-tree [Pre-Order(node->right)].3. Inspect node [Post-order(node)] |
Stack |
O(N) |
| Tree |
Level-order Traversal |
1. Explore root and store the children nodes in queue Q1.2. Explore all nodes in Q1 while storing their children in the queue Q2.3. Explore all nodes in Q2 while storing their children in Q1. Continue with step 2 and 3 till both the queue Q1 and Q2 are empty. |
Queue |
O(N) |
| Tree / Graph |
Breadth First Search (BFS) |
Explore each adjacent node before moving to next level(s) |
Queue |
O(E+V) |
| Tree / Graph |
Depth First Search (DFS) |
Explore first adjacent node before moving to next level(s) |
Stack |
O(E+V) |
| Graph (DAG) |
Topological Sorting |
Edge relaxation in topological order |
Stack |
O(E+V) |