C#. BinarySearchTree – Traverse ways

Source

In this example binary tree is built… we just take a look on traversies

Binary Search Tree

A Binary Search Tree is a binary tree with a search property where elements in the left sub-tree are less than the root and elements in the right sub-tree are greater than the root.

Ex

Binary Search Tree

Walking (Traversing) a Binary Search Tree

There can be 3 types of tree traversals in a binary tree as below.

  • Pre-Order
  • In-Order
  • Post-Order

Pre-Order traversal

In this traversal the traversal happens in the following order.

  • Root node
  • Left Child
  • Right Child

For the binary search tree, displayed above the Pre-Order traversal would be as follows.

Pre-Order traversal

The C# implementation for the same is as follows.

public void PreOrder_Rec (TNode root)

{

if (root != null)

{

Console.Write(root.Data +” “);

PreOrder_Rec(root.Left);

PreOrder_Rec(root.Right);

}

}

In-Order traversal

In this traversal the traversal happens in following order:

  • Left Child
  • Root node
  • Right Child

For the binary search tree, displayed above the In-Order traversal would be as follows.

In-Order traversal

The C# implementation for that is as follows.

public void InOrder_Rec(TNode root)

{

if (root != null)

{

InOrder_Rec(root.Left);

Console.Write(root.Data +” “);

InOrder_Rec(root.Right);

}

}

Post-Order traversal

In this traversal the traversal happens in the following order:

  • Left Child
  • Right Child
  • Root node

For the binary search tree, displayed above the Post-Order traversal would be as follows.

Post-Order traversal

The C# implementation for that is as follows:

public void PostOrder_Rec(TNode root)

{

if (root != null)

{

PostOrder_Rec(root.Left);

PostOrder_Rec(root.Right);

Console.Write(root.Data +” “);

}

}

 Important Notes

  • One of the practical uses of pre-order traversal can be a table of contents in a book where we first visit the root or main chapter then its sub-chapters.
  • One of the practical uses of post-order traversal can be calculating the size of directories in a computer where the first size of its sub-folders are calculated and then it gets assigned to the root folder.
  • Pre-Order and Post-Order traversal can be used in any general tree however In-Order is specific to binary trees.
  • We can form a binary tree if Pre-Order and In-Order traversal or Post-Order and In-Order traversals are given.
  • We can also form a binary tree if Pre-Order and Post-Order traversals are given provided each internal node of the binary tree has two children.
This entry was posted in C#. Bookmark the permalink.

Leave a Reply