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 Lowest Common Ancestor (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)).

1. Left Rotation

2. 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.

#blog #interview #placement #learn #computer #science