- prioritize depth by traversing as deep as we can in one direction
- before backtracking to find other directions
- preorder, inorder, postorder are all DFS but just different timepoints of activating a piece of logic
- **different times of activating logic**
- Preorder traversal
- logic is done on **current** node before moving to children
- **before children**
- Inorder traversal ([[Binary Trees|Binary Tree]] specific)
- call left child first, perform logic, then call right child
- **in between children**
- Postorder traversal
- call all children first, then perform logic on the current node
- so root is the last node where logic is performed
- **after children**
- you can implement recursively and iteratively
- for iteratively, preorder is much less complicated than postorder & inorder
- note for iteratively, visit order is the opposite of insertion order
- implemented with a [[Stacks|Stack]] (recursion uses stack under the hood)
- for [[Trees|Tree]]
- time complexity is $O(n * k)$, where $n$ is total # of nodes, & $k$ is amount of work done at each node (usually $O(1)$)
- $e$ is just $n-1$ in a tree, so gets dominated by $n$ nodes (not the case for below)
- for [[Graphs|Graph]]
- time complexity is $O(n + e)$
- in worst case where node is connected with every other node $e = n^2$
- space complexity is $O(n + e)$
- below is code for iterative [[Graphs|Graph]] DFS
```
def dfs(start):
stack = [start]
while stack:
node = stack.pop()
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
stack.append(neighbor)
```
- below is inorder [[Trees|Tree]] traversal
```
def inOrder(root):
current = root
stack = []
while True:
if current is not None:
stack.append(current)
current = current.left
elif(stack):
current = stack.pop()
print(current.data, end=" ")
current = current.right
else:
break
```
https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/