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.

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.

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.