| Abstract Data Type | Algorithm | Algorithm Gist | Data Structure Used | Time Complexity |
|---|---|---|---|---|
| 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) |
© 2019-2026 Algotree.org | All rights reserved.
This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org
"Experience is the name everyone gives to their mistakes. - Oscar Wilde"