Tree & Graph Traversal

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)