West Hollywood, LA

I recently revisited the DFS tree traversal and decided to summarize what I relearnt

# Algorithm

Algorithmically, DFS (on a Binary Tree) can be expressed as a simple recursive function -

- traverse(node)
- traverse(node.left)
- process(node)
- traverse(node.right)

The order of the steps within the function changes depending on the flavor of the DFS used -

- In order
- Pre order
- Post order

# Depth First

The name of the algorithm is a little confusing, however here are my main takeaways -

- DFS does
**not**stipulate that we start with thenode.**deepest**leaf - We process nodes with a
**bias**towards processing the deeper nodes - The general direction is from left of the tree towards the right of the tree.

#### Inorder

#### Preorder

# A non recursive method

The recursive solution is easy to understand and remember, however in an alternative solution it is also possible to utilize a stack to keep track of nodes that need to be processed.

The general idea -

- Traverse all the left nodes whilst saving the nodes in a stack
- When you reach the end (null), process the top of the stack.
- This should be the left most node in the traversal
- Now repeat this process with the right node of the just processed node

Here is part of the source for an in order traversal from https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/

```
// traverse the tree
while (curr != null || s.size() > 0)
{
/* Reach the left most Node of the
curr Node */
while (curr != null)
{
/* place pointer to a tree node on
the stack before traversing
the node's left subtree */
s.push(curr);
curr = curr.left;
}
/* Current must be NULL at this point */
curr = s.pop();
System.out.print(curr.data + " ");
/* we have visited the node and its
left subtree. Now, it's right
subtree's turn */
curr = curr.right;
```

}