March 26, 2017

* 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.

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

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.

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

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.

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

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.