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.

In-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

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

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.

Conclusion

Typical use cases for

1. **In-Order: **You'd typically use this method to sort or search a value inside a tree
2. 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.
3. Post-Order: You'd typically use this when you need to access leaves first.
   1. A use case is when you process a post-fix notation equation.
   2. 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.