### 2017-03-26

**Depth-First Tree Traversal**

* blogentry, programming, inorder, postorder*

* blogentry, programming, inorder, postorder*

Featured Image - "tree" by AmishHomo, used under CC BY 2.0

The full working source code is available on GitHub

I've forgotten most of the data structure concepts, especially a Tree structure. So I've been re-learning these concepts and would like to share how to traverse a Tree object.

There are two search methods, depth-first, and breath-first. I will only talk about depth-first search methods operating on a binary tree. A binary search tree is where "left node < parent < right node" as shown below.

There are three depth-first search methods; In-order, Pre-order, and Post-order.

This is a most common case of traversing. In-Order in the order the nodes are stored. For the tree above, the list would contain "1 2 3 4 5 6 7".

The implementation looks like the following.

```
1private static void InOrderTraversal(TreeNode<int> node, List<int> list)2{3 if (node == null) return;4
5 InOrderTraversal(node.Left, list);6 list.Add(node.Value);7 InOrderTraversal(node.Right, list);8}
```

The function processes left, parent, and then right nodes.

The first processed node is the leftmost leaf and the last one, rightmost leaf.

Pre-order traverses parent, left, then right, so the list would contain "4 2 1 3 6 5 7".

The code looks like following.

```
1private static void PreOrderTraversal(TreeNode node, List list)2{3 if (node == null) return;4
5 list.Add(node.Value);6 PreOrderTraversal(node.Left, list);7 PreOrderTraversal(node.Right, list);8}
```

The function processes parent, left, and then right nodes.

The first processed is the root, while the last one is the rightmost leaf.

Post-order traverses left, right, then parent so the list contains "1 3 2 5 7 6 4".

Following implements the post-order traversal using recursion.

```
1private static void PostOrderTraversal(TreeNode<int> node, List<int> list)2{3 if (node == null) return;4
5 PostOrderTraversal(node.Left, list);6 PostOrderTraversal(node.Right, list);7 list.Add(node.Value);8}
```

The function processes left, right, and then the parent nodes.

The first to be processed is the leftmost leaf, and the last one is root.

Typical use cases for

- **In-Order: **You'd typically use this method to sort or search a value inside a tree
**Pre-Order:**I don't see much use cases for this other than converting a math notation to a prefix notation, which I don't see many use cases for.**Post-Order:**You'd typically use this when you need to access leaves first.- A use case is when you process a post-fix notation equation.
- You can also use this to delete references in, say, dependency injection tree. You need to delete child references and then their parents so that no memory would be leaked.