Data Structures and Algorithms (DSA) using C# .NET Core — Binary Trees and Binary Search Tree (BST) Tree Traversal- II

Now that we have understood the basics of Tree & Binary Search Tree, the question is how we can read the data from each node, add a node, delete a node or search node (data) in a tree. To read data, we need to visit every node in the tree and this is called Tree Traversing. For e.g. in Fig.1 you want to display the data of each node in the tree, for that you need to visit each node and display the value.

In linear data structures like linked list, arrays, stacks and queues, the data is stored in sequential manner and there is only one way to read the data, but in case of Trees the data is organized in hierarchical manner and so you can traverse (visit) nodes in different ways.

Let see how we can read data in different ways from Tree in Fig.1

Starting from top (left to right): 1, 10, 4, 6, 8

Starting from bottom (left to right): 4, 6, 10, 8, 1

Note: Although we are reading the values from each node in the tree, we are not following the tree hierarchy — parent and child relationship. We can use the traversal methods that take into account the tree hierarchy i.e. the structure of tree — parent and child. For that lest consider we have a node class with data field to store data, a left node and a right node to pointing to the next node ( if any), thus each left and right node can further be thought as sub-tree (node).

 internal class Node
  {
     internal int data;
     internal Node left;
     internal Node right;
     internal Node(int key)
      {
          data = key;
          left = null;
          right = null;
      }
  }    
    
 internal class TreeTraversal
  {
    internal Node root;
    internal TreeTraversal()
    {
        root = null;
    }
  }

Depending on the order in which we want to traverse (visit), there can be 3 types of traversal:

Preorder traversal

1. First visit the root node
2. then visit all the nodes in the left subtree
3. finally visit all the nodes in the right subtree

static void PreorderTraversal(Node node)
  {
      if (node == null)
          return;
      // Traverse root
      Console.Write(node.data + " => ");
      // Traverse left
      PreorderTraversal(node.left);
      // Traverse right
      PreorderTraversal(node.right);
  }

1 => 10 => 4 => 6 => 8 =>

Inorder traversal

1. First visit all the nodes in the left subtree
2. then visit the root node
3. finally visit all the nodes in the right subtree

static void InorderTraversal(Node node)
 {
     if (node == null)
         return;
     // Traverse left
     InorderTraversal(node.left);
     // Traverse root
     Console.Write(node.data + " => ");
     // Traverse right
     InorderTraversal(node.right);
 }

4 => 10 => 6 => 1 => 8 =>

Postorder traversal

1. First visit all the nodes in the left subtree

2. then visit all the nodes in the right subtree

3. Finally visit the root node

static void PostorderTraversal(Node node)
 {
     if (node == null)
         return;
     // Traverse left
     PostorderTraversal(node.left);
     // Traverse right
     PostorderTraversal(node.right);
     // Traverse root
     Console.Write(node.data + " => ");
 }

4 => 6 => 10 => 8 => 1 =>

Source Code:

using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BinarySearchTreeDemo
{
    internal class Node
    {
       internal int data;
       internal Node left;
       internal Node right;
        internal Node(int key)
        {
            data = key;
            left = null;
            right = null;
        }
    }    
    
    internal class TreeTraversal
    {
        internal Node root;
        internal TreeTraversal()
        {
            root = null;
        }
    }

    internal class Program
    {
        static void PreorderTraversal(Node node)
        {
            if (node == null)
                return;
            // Traverse root
            Console.Write(node.data + " => ");
            // Traverse left
            PreorderTraversal(node.left);
            // Traverse right
            PreorderTraversal(node.right);
        }
        static void InorderTraversal(Node node)
        {
            if (node == null)
                return;
            // Traverse left
            InorderTraversal(node.left);
            // Traverse root
            Console.Write(node.data + " => ");
            // Traverse right
            InorderTraversal(node.right);
        }
        static void PostorderTraversal(Node node)
        {
            if (node == null)
                return;
            // Traverse left
            PostorderTraversal(node.left);
            // Traverse right
            PostorderTraversal(node.right);
            // Traverse root
            Console.Write(node.data + " => ");
        }

        static void Main(string[] args)
        {
            TreeTraversal tree = new TreeTraversal();
            tree.root = new Node(1);
            tree.root.left = new Node(10);
            tree.root.right = new Node(8);
            tree.root.left.left = new Node(4);
            tree.root.left.right = new Node(6);



            Console.Write("\n Preorder Traversal: ");
            PreorderTraversal(tree.root);
            Console.WriteLine("\n");
            Console.Write("\n Inorder Traversal: ");
            InorderTraversal(tree.root);
            Console.WriteLine("\n");
            Console.Write("\n Postorder Traversal: ");
            PostorderTraversal(tree.root);

            Console.Read();

        }
    }
}