Tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.

Tree Traversal Algorithms can be classified broadly in the following two categories by the order in which the nodes are visited

• Depth-First Search (DFS) Algorithm : It starts with the root node and first visits all nodes of one branch as deep as possible of the chosen Node and before backtracking, it visits all other branches in a similar fashion. There are three subtypes under this. They are Inorder Traversal , Preorder Traversal , Postorder Traversal

• Breadth-First Search (BFS) Algorithm : It also starts from the root node and visits all nodes of current depth before moving to the next depth in the tree. Level Order Traversal is a type of BFS algorithm.

Inorder Traversal

Steps to be followed in a recursive manner to complete the inorder traversal.

1. Go to left-subtree
2. Visit Node

3. Go to right-subtree

   If it’s a binary search tree, then an in-order traversal lists each item in sorted order.

Preorder Traversal

Steps to be followed in a recursive manner to complete the Preorder traversal.

1. Visit Node
2. Go to left-subtree
3. Go to right-subtree

Postorder Traversal

The sequence of the steps will be…

1. Go to left-subtree
2. Go to right-subtree
3. Visit Node

Level Order Traversal

The breadth of the tree takes priority first and then moves to depth. In simple words, we will visit all the nodes present at the same level one-by-one from left to right and then move to the next level to visit all the nodes of that level.

public class TreeNode<T>
{
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    public TreeNode(T data)
    {
        this.data = data;
        this.left = this.right = null;
    }

    public void inorderTraversal(TreeNode<T> root)
    {
        if (root != null)
        {
            inorderTraversal(root.left);
            Console.WriteLine(root.data + " ");
            inorderTraversal(root.right);
        }
    }

    public void preorderTraversal(TreeNode<T> root)
    {
        if (root != null)
        {
            Console.WriteLine(root.data + " ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
    }

    public void postorderTraversal(TreeNode<T> root)
    {
        if (root != null)
        {
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            Console.WriteLine(root.data + " ");
        }
    }

    public void levelorderTraversal(TreeNode<T> root)
    {
        if (root == null)
        {
            return;
        }

       var queue = new Queue<TreeNode<T>>();
        queue.Enqueue(root);
        var currentNode = root;
        if (queue.Any() == false && currentNode != null)
        {
            if (currentNode.left != null)
            {
                queue.Enqueue(currentNode.left);
            }

            if (currentNode.right != null)
            {
                queue.Enqueue(currentNode.right);
            }
            Console.Write(" {0} ", currentNode.data);
            queue.Dequeue();
            currentNode = queue.Dequeue();
        }
        else
        {
            throw new Exception("Empty tree");
        }
   }