by A Binary Search Tree is a Binary tree in which all the nodes has following properties.
- Left subtree of a node contains all the nodes having values lesser than the node.
- Right subtree of a node contains all the nodes having values higher than the node.
- Both the left and right subtree is also a Binary Search Tree.
As the name suggests, this data structure is mainly used for faster searching. In order to do that, restrictions are applied while inserting/deleting an element into the tree. As a result of these restrictions, worst case search time complexity remains at O(log n). Before going ahead have a look into Binary Search Tree basics, Binary Search Tree Insert, Binary Search Tree Delete, Binary Search Tree Search operations.
Let’s have a look into basic C++ class definition for Binary Search Tree.
template <typename T>
class BinarySearchTree
{
public:
T m_data;
BinarySearchTree* m_left;
BinarySearchTree* m_right;
BinarySearchTree (T data);
~BinarySearchTree ();
};
/* Below are some useful functions which we are going to use it in our examples */
template <typename T>
void print_binary_tree_inorder (BinarySearchTree<T>* root)
{
if (root -> m_left)
print_binary_tree_inorder (root -> m_left);
cout << " " << root -> m_data;
if (root -> m_right)
print_binary_tree_inorder (root -> m_right);
}
template <typename T>
void print_tree (BinarySearchTree<T>* root)
{
cout << "Binary tree contents: ";
print_binary_tree_inorder (root);
cout << endl;
}
/* Simply used this function to delete all nodes and free memory */
template <typename T>
void delete_all_nodes (BinarySearchTree<T>* root)
{
if (!root)
return;
if (root -> m_left)
{
delete_all_nodes (root -> m_left);
}
if (root -> m_right)
{
delete_all_nodes (root -> m_right);
}
delete root;
}
Finding Kth Minimum value in a Binary Search Tree
In Binary Search Tree data is stored in a particular manner due to which inorder traversal of Binary Search Tree will provide a sorted list. Based on the property of Binary Search Tree in which left node is lower than root node which is lower than right node, we will traverse the Binary Search Tree in a manner to find out the Kth Smallest Value. Inorder traversal of a Binary Search Tree produces a sorted list, which can be used here.
Let’s take an example to understand the working of above algorithm to find out the 4th node with minimum value.
- Start with the root element “47”.
- Move towards left child “34”.
- Move towards left child “17”. This is the left most child and hence would be the smallest node in BST.
- Return to parent node “34”. This is the 2nd smallest node in BST (Check Property).
- Move towards right child if available will take us to “38”.
- If this node “38” has a left child then go towards that otherwise this node would be the next smallest node. Hence, this is 3rd smallest node.
- Move towards right child if available will take us to “41”.
- If this node “41” has a left child then go towards that otherwise this node would be the next smallest node. Moving towards “40”.
- If this node “40” has a left child then go towards that otherwise this node would be the next smallest node. Hence, this is 4th smallest node.
Let’s look into the sample code.
template <typename T>
BinarySearchTree<T>* find_kth_minimum_element_in_bst (BinarySearchTree<T>* root, int k, int* count)
{
if (!root)
return NULL;
BinarySearchTree<T>* temp = find_kth_minimum_element_in_bst (root -> m_left, k, count);
if (temp)
return temp;
++(*count);
if (*count == k)
return root;
return find_kth_minimum_element_in_bst (root -> m_right, k, count);
}
Few of the functions defined below are explained in Binary Search Tree Insert Operation Explanation and Binary Search Tree Delete Operation Explanation. Let’s look into the sample main function which utilizes Binary Search Tree class definition and iterative functions defined above.
int main ()
{
BinarySearchTree<int>* root = new BinarySearchTree<int> (33);
insert_element_in_bst_recursive (20, root);
insert_element_in_bst_recursive (10, root);
insert_element_in_bst_recursive (30, root);
insert_element_in_bst_recursive (40, root);
insert_element_in_bst_recursive (50, root);
insert_element_in_bst_recursive (43, root);
insert_element_in_bst_recursive (77, root);
insert_element_in_bst_recursive (69, root);
insert_element_in_bst_recursive (25, root);
insert_element_in_bst_recursive (11, root);
insert_element_in_bst_recursive (10, root);
insert_element_in_bst_recursive (5, root);
insert_element_in_bst_recursive (18, root);
insert_element_in_bst_recursive (67, root);
insert_element_in_bst_recursive (88, root);
insert_element_in_bst_recursive (99, root);
insert_element_in_bst_recursive (65, root);
insert_element_in_bst_recursive (58, root);
insert_element_in_bst_recursive (51, root);
insert_element_in_bst_recursive (77, root);
print_tree (root);
search_element_in_bst_recursive (57, root);
search_element_in_bst_recursive (20, root);
search_element_in_bst_recursive (50, root);
BinarySearchTree<int>* min = find_minimum_element_in_bst_using_recursion (root);
BinarySearchTree<int>* max = find_maximum_element_in_bst_using_recursion (root);
cout << " Minimum element in BST: " << min -> m_data << endl;
cout << " Maximum element in BST: " << max -> m_data << endl;
int count = 0;
int k = 4;
BinarySearchTree<int>* k_min = find_kth_minimum_element_in_bst (root, k, &count);
cout << k << "th Minimum element in BST: " << k_min -> m_data << endl;
BinarySearchTree<int>* parent = NULL;
root = delete_element_in_bst_recursive (20, root, parent);
print_tree (root);
root = delete_element_in_bst_recursive (33, root, parent);
print_tree (root);
root = delete_element_in_bst_recursive (10, root, parent);
print_tree (root);
root = delete_element_in_bst_recursive (77, root, parent);
print_tree (root);
root = delete_element_in_bst_recursive (135, root, parent);
print_tree (root);
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 10 10 11 18 20 25 30 33 40 43 50 51 58 65 67 69 77 77 88 99
Data: 57 not found in BST !!!
Data: 20 found in BST !!!
Data: 50 found in BST !!!
Minimum element in BST: 5
Maximum element in BST: 99
4th Minimum element in BST: 11
Data: 20 found in BST, node will be deleted now !!!
Binary tree contents: 5 10 10 11 18 25 30 33 40 43 50 51 58 65 67 69 77 77 88 99
Data: 33 found in BST, node will be deleted now !!!
Binary tree contents: 5 10 10 11 18 25 30 40 43 50 51 58 65 67 69 77 77 88 99
Data: 10 found in BST, node will be deleted now !!!
Binary tree contents: 5 10 11 18 25 30 40 43 50 51 58 65 67 69 77 77 88 99
Data: 77 found in BST, node will be deleted now !!!
Binary tree contents: 5 10 11 18 25 30 40 43 50 51 58 65 67 69 77 88 99
Data: 135 not found in BST !!!
Binary tree contents: 5 10 11 18 25 30 40 43 50 51 58 65 67 69 77 88 99
