Data Structures : Tree Traversals

(Week 2)

Tree traversals are one of the most important algorithm in computer science because sometimes we don't have linear data structure in that they are organized through in relationship or hierarchy. 

This allows us to traverse them in multiple ways. To clarify, tree traversal refers to the process of visiting each individual node exactly once. For our traversal, we will focus on binary trees, which are trees that have a max of two children. You can check out my earlier post on binary search trees. 

There are two types of traversal algorithm, Depth First and Breath First algorithms. Today, I am going to try to demonstrate Depth First Traversal which actually splits into 3 different algorithm. 

There are three types of depth-first traversal:

pre-order: visit the parent, then all the left children, and then all the right children. Pre-order traversal while duplicating nodes and values can make a complete duplicate of a binary tree. It can also be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly.

in-order: visit the left child, then the parent, and then the right child. This approach is useful for BSTs as it traverses the nodes in sorted order.  Also in-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).

post-order: visit the left child, then the right child, and then the parent; however, post-order traversal while deleting or freeing nodes and values can delete or free an entire binary tree. It can also generate a postfix representation of a binary tree.

For depth-first traversal, we will require a stack data structure, which follows a Last In, First Out (LIFO) rule. For example ; You can think of a stack as a stack of newspapers; the newspaper on top was the last added to the pile, but the first to be grabbed by a customer for purchase. 

Lets see with example :  on Github