Post
Ask Question

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 and Binary Search Tree, the question is how we can read the data from each node, add a node, delete a node, or search a 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.

Tree Traversal

Fig 1. Tree Traversal

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

Let's 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 the tree — parent and child. For that last, consider we have a node class with a data field to store data, a left node, and a right node to point to the next node ( if any). Thus, each left and right node can further be thought of as a 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();

        }
    }
}


Similar Articles