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.