Post

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

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;

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);