Binary Search Tree:
A Binary Search Tree is a binary tree with search properties where elements in the left sub-tree are less than to the root and elements in the right sub-tree are greater than to the root.
For example:
Searching an Element in a Binary Search Tree (BST)
To find an element in a Binary Search Tree, we first need to compare the element with the root node; if it matches then we have the right node otherwise we need to check the left or right.
The C# implementation of that same is as follows.
|
public object SearchElement_Rec(objectelement, TNoderoot)
{
current = root;
if (current == null)
return "Not found";
if (Convert.ToInt32(element)== Convert.ToInt32(current.Data))
return element;
if (Convert.ToInt32(element)< Convert.ToInt32(current.Data))
return this.SearchElement_Rec(element,current.Left);
else
return this.SearchElement_Rec(element,current.Right);
} |
The following is the test result of the implementation.
|
Input: Console.WriteLine(bst.SearchElement_Ite(15));
Output:
Input: Console.WriteLine(bst.SearchElement_Ite(19));
Output:  |
Find a Minimum Element in a Binary Search Tree (BST)
Finding a minimum element in a BST is simple, we just need to access the leftmost element; it is the minimum element.
The C# implementation of that is as follows.
|
public object TreeMin_Rec(TNode root)
{
current = root;
if (current.Left == null)
{
return current.Data;
}
returnTreeMin_Rec(current.Left);
} |
The following is the result of the implementation.
|
Input: Console.WriteLine(bst.TreeMin_Rec(bst.ReturnRoot()));
Output: |
Find a Maximum Element in a Binary Search Tree (BST)
Finding a maximum element in a BST is simple, we just need to access the rightmost element; it is the maximum element.
The C# implementation of that is as follows.
|
public object TreeMax_Rec(TNode root)
{
current = root;
if (current.Right == null)
{
return current.Data;
}
returnTreeMax_Rec(current.Right);
} |
The following is the result of the implementation.
|
Input: Console.WriteLine(bst.TreeMax_Rec(bst.ReturnRoot()));
Output: |
Find a Successor Element in a Binary Search Tree (BST)
Finding the successor element is a bit tricky. There can be two cases to consider here.
-
Right-sub tree is not null:
If the right sub-tree is not null then to find a successor element, we need to find the minimum of the right sub-tree. To find a minimum element of the right sub-tree we can use the TreeMin_Rec method shown above.
-
Right-sub tree is null:
If right sub-tree is null then we need to find the successor differently. We need to start from the node (for that we need the successor) and move upwards as long as the current node is on the right of its parent. The moment the current node turns left to its parent, the parent is the successor (if it’s not null).
The C# implementation of that is as follows.
|
public objectTreeSuccessor_Ite(object element)
{
////Get the Node object for an element
current = this.GetNode(element);
if (current!=null)
{
if (current.Right!= null)
returnthis.TreeMin_Rec(current.Right);
else
{
tempParent = current.Parent;
while((tempParent != null) && (current == tempParent.Right))
{
current = tempParent;
tempParent = tempParent.Parent;
}
if(tempParent != null)
returntempParent.Data;
else
return"Successor is not found!";
}
}
else
{
return "Please enter the valid tree element!";
}
} |
The following is the result of the implementation. This covers the described two cases (in other words when the right sub-tree is available (element: 20) and when it’s not (element: 16). and when the successor is not available (element: 45).
|
Input: Console.WriteLine(bst.TreeSuccessor_Ite(20));
Output:
Input: Console.WriteLine(bst.TreeSuccessor_Ite(16));
Output:
Input: Console.WriteLine(bst.TreeSuccessor_Ite(45));
Output: |
Find a Predecessor Element in a Binary Search Tree (BST)
Finding the predecessor element is just the opposite of finding the successor (just interchange the roles of left and right). There can be two cases to consider here as well.
-
Left-sub tree is not null:
If the left sub-tree is not null then to find a predecessor element, we need to find the maximum of the left sub-tree. To find a maximum element of a left sub-tree we can use the TreeMax_Rec method shown above.
-
Left-sub tree is null:
If the left sub-tree is null then we need to find the predecessor differently. We need to start from the node (for that we need the predecessor) and move upwards as long as the current node is on the left of its parent. The moment the current node turns right to its parent, the parent is the predecessor (if it’s not null).
The C# implementationof that is as follows.
|
public objectTreePredecessor_Ite(object element)
{
////Get the Node object for an element
current = this.GetNode(element);
if (current != null)
{
if (current.Left != null)
return this.TreeMax_Rec(current.Left);
else
{
tempParent = current.Parent;
while((tempParent != null) && (current == tempParent.Left))
{
current = tempParent;
tempParent = tempParent.Parent;
}
if(tempParent != null)
returntempParent.Data;
else
return"Predecessor is not found!";
}
}
else
{
return "Please enter the valid tree element!";
}
} |
The following is the result of the implementation. This covers the described two cases (in other words when the left sub-tree is available (element: 20) and when it’s not (element: 16) and when the predecessor is not available (element: 13).
|
Input: Console.WriteLine(bst.TreePredecessor_Ite(20));
Output:
Input: Console.WriteLine(bst.TreePredecessor_Ite(16));
Output:
Input: Console.WriteLine(bst.TreePredecessor_Ite(13));
Output: |
Appreciate your comments/suggestions.
Kevin SchaalPosted Jun 8, 2022, 4:50 PM
Hi Prakash, thank you for the post! I have released a BST library that might be useful for people reading this: https://github.com/m31coding/M31.BinarySearchTrees Have a good day and keep up the good work!
kazmi aliPosted Jun 25, 2017, 8:57 AM
Very well explained... Search Element in Binary Search Tree with step by step explanation : https://youtu.be/7v-6447o5Q8
Prakash TripathiPosted Mar 6, 2016, 10:27 PM
Thnx Kumaresh.
Prakash TripathiPosted Mar 6, 2016, 10:26 PM
Thnx Karthiga.
Kumaresh RajalingamPosted Mar 6, 2016, 8:25 PM
good one
Kumaresh RajalingamPosted Mar 6, 2016, 8:25 PM
Nice explanation
Sr KarthigaPosted Mar 6, 2016, 8:13 PM
good one
Sr KarthigaPosted Mar 6, 2016, 8:13 PM
Nice explanation
Prakash TripathiPosted Feb 25, 2016, 7:28 AM
Thnx Sonu.
Sonu ChaudharyPosted Feb 25, 2016, 7:16 AM
nice article