# Placement Practice - Binary Search Tree

We have already covered the definition of BST, insertion, and deletion of nodes from the tree __click here__.

Let's look at the process of finding LCA in a Binary Search Tree.

Finding LCA in Binary Search Tree

The **LCA** or **Lowest Common Ancestor** of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.

Given values of two values n1 and n2 in a Binary Search Tree, find the **L**owest **C**ommon **A**ncestor (LCA). For Simplicity, you may assume that both the values exist in the tree.

Consider the below BST:

In the of above BST:

```
LCA of 4 and 7 is 6
LCA of 7 and 3 is 3
LCA of 4 and 10 is 8
```

The main idea would be

While traversing from top to bottom, the first node

**n**we encounter with a value between**n1**and**n2**, i.e.,**n1 <= n <= n2**, is LCA of n1 and n2 (assuming that n1 < n2).So just recursively traverse the BST, if node's value is greater than both n1 and n2 then our LCA lies in the left subtree of the node, if it's is smaller than both n1 and n2, then LCA lies on the right subtree.

Otherwise, the root is LCA (assuming that both n1 and n2 are present in BST).

**Implementation using C++:**

```
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node* left, *right;
};
node *lca(node* root, int n1, int n2)
{
if (root == NULL) return NULL;
if (root->data > n1 && root->data > n2)
return lca(root->left, n1, n2);
if (root->data < n1 && root->data < n2)
return lca(root->right, n1, n2);
return root;
}
node* newNode(int data)
{
node* Node = new node();
Node->data = data;
Node->left = Node->right = NULL;
return(Node);
}
int main()
{
node *root = newNode(200);
root->left = newNode(80);
root->right = newNode(220);
root->left->left = newNode(40);
root->left->right = newNode(120);
root->left->right->left = newNode(100);
root->left->right->right = newNode(140);
int n1 = 100, n2 = 140;
node *t = lca(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2
<< " is " << t->data<<endl;
n1 = 140, n2 = 80;
t = lca(root, n1, n2);
cout<<"LCA of " << n1 << " and " << n2
<< " is " << t->data << endl;
n1 = 100, n2 = 220;
t = lca(root, n1, n2);
cout << "LCA of " << n1 << " and " << n2
<< " is " << t->data << endl;
return 0;
}
```

**Output:**

```
LCA of 100 and 140 is 120
LCA of 140 and 80 is 80
LCA of 100 and 220 is 200
```

AVL Tree

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

**Insertion**

To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).

Left Rotation

Right Rotation

Below image shows how insertion is performed:

**Time Complexity:**

The rotation operations (left and right rotate) take constant time as only a few pointers are being changed there.

Updating the height and getting the balance factor also takes constant time.

So the time complexity of the AVL insert remains the same as BST insert which is O(h) where h is the height of the tree.

Since the AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).

Happy Coding!

Follow us on Instagram __@programmersdoor__

Join us on Telegram __@programmersdoor__

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.