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;
}
Lowest Common Ancestor in Binary Search Tree
The Lowest Common Ancestor of two node “A” and “B” in Binary Search Tree is defined as the lowest node in Binary Search Tree who is the ancestor of both node “A” and “B”.
In other words, LCA is the node farthest from the root node whos is the ancestor of both node “A” and “B”.
Algorithm
- Start traversing from root.
- If the low value node is smaller than root and high value node is higher than root then root is the LCA of node low and high. return this node.
- If both low and high values are higher than root node value then move towards right child.
- If both low and high values are lower than root node value then move towards right child.
- Repeat above 3 steps.
Let’s take an example to understand the working of above algorithm.
In above Binary Search Tree,
- LCA of node “17” and “40” is “34”.
- LCA of node “17” and “61” is “47”.
- LCA of node “58” and “63” is “58”.
Let’s look into the sample code.
template <typename T>
BinarySearchTree<T>* find_least_common_ancestor_in_bst (BinarySearchTree<T>* root, BinarySearchTree<T>* low, BinarySearchTree<T>* high)
{
if (root -> m_data >= low -> m_data && root -> m_data <= high -> m_data)
return root;
else if (root -> m_data >= high -> m_data)
return find_least_common_ancestor_in_bst (root -> m_left, low, high);
else
return find_least_common_ancestor_in_bst (root -> m_right, low, high);
}
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 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;
count = 0;
k = 10;
BinarySearchTree<int>* k_max = find_kth_maximum_element_in_bst (root, k, &count);
cout << k << "th Maximum element in BST: " << k_max -> m_data << endl;
BinarySearchTree<int>* low = search_element_in_bst_recursive (18, root);
BinarySearchTree<int>* high = search_element_in_bst_recursive (30, root);
BinarySearchTree<int>* lca = find_least_common_ancestor_in_bst (root, low, high);
cout << " LCA node of " << low -> m_data << " and " << high -> m_data << " is: " << lca -> m_data << endl;
low = search_element_in_bst_recursive (51, root);
high = search_element_in_bst_recursive (77, root);
lca = find_least_common_ancestor_in_bst (root, low, high);
cout << " LCA node of " << low -> m_data << " and " << high -> m_data << " is: " << lca -> m_data << endl;
low = search_element_in_bst_recursive (40, root);
high = search_element_in_bst_recursive (99, root);
lca = find_least_common_ancestor_in_bst (root, low, high);
cout << " LCA node of " << low -> m_data << " and " << high -> m_data << " is: " << lca -> 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
10th Maximum element in BST: 50
Data: 18 found in BST !!!
Data: 30 found in BST !!!
LCA node of 18 and 30 is: 20
Data: 51 found in BST !!!
Data: 77 found in BST !!!
LCA node of 51 and 77 is: 77
Data: 40 found in BST !!!
Data: 99 found in BST !!!
LCA node of 40 and 99 is: 40
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
