Monthly Archives: January 2016

Rotate an Array

Rotate an Array

This post deals with the question of how to rotate an array?

Rotate an Array problem Statement :

Given an array ,we need to rotate the array the specified number of times. Array rotation can be done in 2 ways.

Rotate an Array example:

 Rotate an Array

Rotate an Array Solution:

Method 1:

This is the simplest way to solve the problem.

Algorithm:

  1. Store the first “d” elements in a temp array.
  2. Shift the elements of the array to the right or the left.
  3. Store the “d” elements back in the array.

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Function to rotate arr[] of size n by d*/
void RotateArray(int arr[], int d, int n)
{
    int temp[d];
 
    /*Storing d elements in temp array*/
     for(int i=0;i<d;i++)
        temp[i]=arr[i];
 
    /*Shifting rest of array*/
     for(int j=0;j<n-d;j++)
        arr[j]=arr[j+d];
 
    /*Storing back d elements*/
     for(int k=n-d,i=0;k<n;k++,i++)
        arr[k]=temp[i];
}

/* Function to print the array */
 void printArray(int arr[], int size)
 {
    for(int i = 0; i < size; i++)
      cout<<arr[i]<<" ";
 }
 
/* Driver program to test above functions */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    printArray(arr,7);
    RotateArray(arr, 3, 7);
    cout<<"\nArray after Rotation is:\n";
    printArray(arr, 7);
    return 0;
}

Output:

1 2 3 4 5 6 7 
Array after Rotation:
4 5 6 7 1 2 3

Time Complexity : O(N)
Auxiliary space:O(d)

Method 2:

We rotate the array one by one by storing the first element in temp variable and move A[1] to A[0]…and temp to A[n-1].

  1. Rotate the array by 1 element.
  2. Repeat the above process “d” times.

We are using left rotation in the solution.

#include <bits/stdc++.h>
using namespace std;
 
/*Function to rotate an array k times*/
void RotateArray(int A[], int d, int n)
{
 for (int i = 0; i < d; i++)
 {
    int j, temp;
  /*Rotating array by one step*/
    temp = A[0];
    for (j = 0; j < n-1; j++)
        A[j] = A[j+1];
    A[j] = temp;
 }
}
 
 /*Function to print the array */
 void printArray(int A[], int size)
 {
   for(int i=0; i < size; i++) 
     cout<<A[i]<<" ";
 } 

/*Driver program to test the above functions*/
int main()
{
   int A[] = {10, 20, 30, 40, 50, 60, 70};
   printArray(A,7);
   RotateArray(A, 4, 7);
   cout<<"\nArray After Rotation \n";
   printArray(A, 7); 
   return 0;
}

Output:

10 20 30 40 50 60 70 
Array After Rotation
50 60 70 10 20 30 40

Time Complexity: O(N*d)
Space Complexity:O(1)

Method 3:

Also known as the juggling algorithm this method extends method 2 and is used to rotate an array.
The algorithm divides the array into some blocks and then it swaps the elements present in the array in the intervals of length of GCD(n,d).
Instead of moving one by one, the array is divided in different sets where number of sets is equal to GCD of n and d and  the elements within sets are moved.
If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[O] and keep moving arr[i+d] to arr[i] and finally store temp at the right place.

Algorithm:

  1. Find GCD of “n” and “d”.Let it be “g”.
  2. Array is divided into consecutive sets containing g elements.
  3. The first element of each set is rotated once.
  4. Then the second element and so on.

Example:

Let the array be arr[]={1,2,3,4,5,6}. Here n=6 and d=2. GCD(6,2)=2

Array after first set elements are rotated. arr[]={3,2,5,4,1,6}
Array after second set elements are rotated. arr[]={3,4,5,6,1,2}

Here is the working code in c++:

#include <bits/stdc++.h>
using namespace std;

/*Function to get gcd of a and b*/
int gcd(int a,int b)
{
 if(b==0)
   return a;
 else
   return gcd(b, a%b);
}
 
/*Function to rotate arr[] of size n by d*/
void RotateArray(int arr[], int d, int n)
{
 int i, j, k, temp;
 for (i = 0; i < gcd(d, n); i++)
 {
 /* move i-th values of blocks */
     temp = arr[i];
     j = i;
     while(1)
    {
       k = j + d;
       if (k >= n)
         k = k - n;
       if (k == i)
         break;
      arr[j] = arr[k];
      j = k;
   }
   arr[j] = temp;
 }
}

/* Function to print the array */
void printArray(int arr[], int size)
{
  for(int i = 0; i < size; i++)
     cout<<arr[i]<<" ";
}

/* Driver program to test above functions */
int main()
{
   int arr[] = {10, 20, 30, 40, 50, 60, 70};
   printArray(arr,7);
   RotateArray(arr, 2, 7);
   cout<<"\nArray after Rotation\n";
   printArray(arr, 7);
   return 0;
}    

Output:

10 20 30 40 50 60 70
Array after Rotation
30 40 50 60 70 10 20

Time Complexity:O(N)
Space Complexity:O(1)
It takes no extra space and its the most efficient algorithm to rotate an array.

Deleting a node from a given position in a Linked List

Deletion of a node from a Linked List at a given position.

Problem statement for deleting a node from Linked List:

 Given a singly linked list, you need to delete a node from a given position.

Deletion of a node from Linked list Example:
Given the following singly linked list-

80->34->19->56->10->62

If the 4th node is to be deleted, the resultant linked list after deletion of the node should be:

80->34->19->10->62

Algorithm to delete a node from a given position in a Linked List:

  1. Find the node at the position before the given position.
  2. Change the next pointer of this node and make it point to the address of the node which is after the node to be deleted.
  3. Free the memory allocated to the node to be deleted.

Video explanation for deleting a node from a given position in a linked list:

Solution code in c++ for deleting a node from a given position in a singly linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct node
{
   int data;
   node * next;
};
 
/*Function that inserts nodes in front of
Given Linked List*/
void InsFront(node **head,int data)
{
   node *temp = new node;
   temp->data = data;
   temp->next = *head;
   *head = temp; 
}

/*Function that will delete the node.
  "pos" is the position of the node 
   to be deleted. */
void DelNode(node **head,int pos)
{
  /*"prev" will point to the node
     whose position is before the node to be deleted.
     "temp" is a copy of head pointer*/
   
   node *temp = *head;
   node *prev;
   /*if head is NULL i.e. linked list 
     is empty */
   if(temp == NULL)
      return;
   /*If the head is the node that is 
   to be deleted*/
   if(pos == 1)
   {
      *head = temp->next;
      delete temp;
      return;
   }
   
   /*Traversing till we find the 
   node to be deleted*/
   for(int i=1 ; i!=pos ; i++)
   {
      prev = temp;
      temp = temp->next;
   }
   
   /*This condition is true, if the 
   data is not present in LL*/
   if(temp == NULL)
   {
      cout<<"Data not present\n";
      return;
   }
   else
   {  
      /*Deletion of the node*/      
      prev->next = temp->next;
      delete temp;
   }
}

/*Function that is used to 
print the Linked List*/
void printList(node *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
   cout<<"NULL";
}

int main()
{
  node* head = NULL;
  InsFront(&head, 62);
  InsFront(&head, 10);
  InsFront(&head, 56);
  InsFront(&head, 19);
  InsFront(&head, 34);
  InsFront(&head, 80);
  
  cout<<"Created Linked list is:\n";
  printList(head);
  
  /*Deleting node at position 4*/
  DelNode(&head,4);
  cout<<"\nResultant Linked list is:\n";
  printList(head);
  
   return 0;
}

Output:

Created Linked list is:
80-> 34-> 19-> 56-> 10-> 62-> NULL 
Resultant Linked list is:
80-> 34-> 19-> 10-> 62-> NULL

Time Complexity of node deletion in a singly linked list: O(n)

Reverse a Linked List

Reverse a Linked List

This post deals with the question how to reverse a linked list? A linked list can be reversed either recursively or iteratively.

Reverse a Linked List Problem Statement:

Given a Linked List and its the pointer to its head, reverse the linked list.

Reverse a Linked List Problem Solution:

Iterative Solution:

Here we use 3 pointers,
current, previous and next.

  1. Change next pointer of current to point to previous.
  2. Make prev = curr, curr = next.
  3. Repeat the above process till we current is not NULL.

Reverse a Linked List Problem Video Explanation:

Reverse a Linked List Problem Solution code in C++:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in
Linked List*/
struct node
{
   int data;
   node * next;
};

/*This function is used to add
new nodes to the Linked List*/
void push(node **head,int data)
{
   node *temp=new node;
   temp->data=data;
   temp->next=*head;
   *head=temp;
}

/*This function is used to
print the Linked List*/
void Print(node *head)
{
   while(head)	
   {
      cout<<head->data<<" ";
      head=head->next;
   }
   cout<<endl;
}

/*This function is used to 
reverse the Linked List*/
void reverse(node **head)
{
   node *prev=NULL;
   node *curr=*head;
   node *next=NULL;
   while(curr)
   {
      next=curr->next;
      curr->next=prev;
      prev=curr;
      curr=next;
   }
   *head=prev;
}

/*driver program to test the 
above function*/
int main() {
   node *head=NULL;
   push(&head, 20);
    push(&head, 4);
    push(&head, 15); 
    push(&head, 85);      
    
    Print(head);    
    reverse(&head); 
    cout<<"The reverse List is: \n";
    Print(head);
   return 0;
}

Output:

Original Linked List:
85 15 4 20 
The reverse List is: 
20 4 15 85

Time Complexity: O(N) where N is the number of nodes in the linked list.


Recursive solution:

Algorithm to reverse a linked list recursively:

  1. Start from the head node, pointed to by “first”.
  2. If the next node is null, return.
  3. Traverse the list recursively.
  4. Set first->next->next to first.
  5. Set first->next to NULL.
  6. Set head to first->next.

Video solution on how to reverse a linked list recursively:

Solution code for reversing a Linked List recursively:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in
Linked List*/
struct node
{
 int data;
 node * next;
};

/*This function is used to add
new nodes to the Linked List*/
void push(node **head,int data)
{
 node *temp = new node;
 temp->data = data;
 temp->next = *head;
 *head = temp;
}

/*This function is used to
print the Linked List*/
void Print(node *head)
{
 while(head) 
 {
 cout<<head->data<<" ";
 head = head->next;
 }
}

/*Function to reverse list*/
void reverse(node** head)
{
 /*first points to head*/
 node* first = *head;
 
 /*rest points to next of first*/
 node* rest = first ->next;
 
 /*if rest is the last node*/
 if (rest == NULL)
 { return; }

 /*recursive function call*/
 reverse(&rest);

 /*makes last node(new head) point
 to second last node(new next)*/
 first->next->next = first; 

 /*removes original links of the list*/
 first->next = NULL; 

 *head = rest; 
}

/*driver program to test the 
above function*/
int main()
{
 node *head = NULL;
 push(&head, 5);
 push(&head, 4);
 push(&head, 3);
 push(&head, 2); 
 push(&head, 1); 
 cout<<" Entered list is: \n";
 Print(head); 
 
 /*calling reverse function*/
 reverse(&head); 
 cout<<"\nThe reverse List is: \n";
 Print(head);
 return 0;
}

Output:

Entered list is: 
1 2 3 4 5 
The reverse List is: 
5 4 3 2 1 

Time Complexity of reversing a linked list recursively is: O(N)
Space Complexity 
of reversing a linked list recursively is: O(1)

Print inorder traversal of a BST represented using array

Print inorder traversal of a Binary Search Tree (BST) represented using array

Given a BST represented by an array, print inorder traversal of this array, i.e. print the elements of the array is such a way, that it represents the inorder Traversal of a BST.

Print inorder traversal of a Binary Search Tree (BST) represented using array Example:

Input:    
              4
           /     \
          2       6
        /  \     /  \
       1    3    5   7
This BST is stored in array as
arr[] = {4, 2, 6, 1, 3, 5, 7}

The Output should be:
1 2 3 4 5 6 7

Print inorder traversal of a Binary Search Tree (BST) represented using array Solution:

When a tree is stored using an array, then if the parent is given by the index i,
Then its
left child is given by index 2*i +1,
right child is given by index 2*i +2.

So, we recursively use first print the left subtree, followed by the present node and then the rescursively the right subtree.
We use the start and end indexes of the array to stop the recursion.

Print inorder traversal of a Binary Search Tree (BST) represented using array code in C++:

#include<bits/stdc++.h>
using namespace std;
 
void printInorder(int a[],int start,int end)
{
   if(start>end)
      return;
   /*Printing the left subtree*/	
   printInorder(a,start*2+1,end);
   
   /*printing present value*/
   cout<<a[start]<<" ";
   
   /*Printing the right subtree*/
   printInorder(a,start*2+2,end);
}
 
int main()
{
  int arr[] = {4, 2, 6, 1, 3, 5, 7};
  int arr_size = sizeof(arr)/sizeof(int);
  cout<<"The InOrder Traversal is:\n";
  printInorder(arr, 0, arr_size-1);
  return 0;
}

 Output:

The InOrder Traversal is:
1 2 3 4 5 6 7

Time Complexity: O(N) as all nodes are visited once.

Remove Binary Search Tree keys outside a given range

Remove Binary Search Tree (BST) keys outside a given range

Or Remove BST keys that don’t lie in given range/remove bina.

Remove BST keys outside a given range Problem Statement:

Given a Binary Search Tree(BST) and a range say [ k1 , k2 ], remove all the nodes, whose values lie outside the given range.
While removing the nodes, the BST property is maintained.

Remove BST keys outside a given range Example:

Input:    
              10
           /      \
          5        20
        /   \      /  \
       1     7    15   25 

Range = [6,22]
Output after Modification:

              10
            /    \
           7      20
                  /  
                 15

Remove Binary Search Tree (BST) keys outside a given range solution:

Here we follow POST-ORDER fashion to remove nodes.
This way when we reach a root node, its children are already processed and we do not need to worry about the sub-trees below this node.

When we find a node that is not in range, there can be two cases that arise:

  1. Node’s data is smaller than the min value.
    Here remove the root, and return the right subtree as the new root.
  2. Node’s data is greater that the max value.
    Here remove the root, and return the left subtree as the new root.

Note that when we return the left/right subtrees, they have already been processed.

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function deletes the nodes whose value 
doesn't lie in range. It follows Postorder fashion*/
node *RemoveKeysNotInRange(node *root,int min,int max)
{
   if(!root)
      return NULL;
   
   /*PostOrder fashion is followed*/
   root->right=RemoveKeysNotInRange(root->right,min,max);
   root->left=RemoveKeysNotInRange(root->left,min,max);
   
   /*These Ifs are self explainatory*/
   if(root->data < min)
   {
      node *temp=root->right;
      delete root;
      return temp;
   }
   if(root->data > max)
   {
      node *temp=root->left;
      delete root;
      return temp;
   }
   return root;
}

int main() {
   /* Let us create following BST
              10
            /    \
           5     20
         /  \    /  \
        1    7  15   25 */
    node *root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);
 
    cout << "Inorder traversal of the given BST is: ";
    Inorder(root);
 
    root = RemoveKeysNotInRange(root, 6, 22);
 
    cout << "\nInorder traversal of the modified BST is: ";
    Inorder(root);
   return 0;
}

Output:

Inorder traversal of the given BST is: 1 5 7 10 15 20 25 
Inorder traversal of the modified BST is: 7 10 15 20

Time Complexity: O(N) as all  nodes are visited once.

Inorder Successor and Predecessor of a given Key in BST

Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST)

Inorder Successor and Predecessor of a given Key in BST Problem Statement:

Given a Binary Search Tree (BST) and a key, you need to tell the values will precede and succeed the given key in the Inorder Traversal.
If the given key doesn’t exist in the BST, then print the values between which the given key will lie.

Inorder Successor and Predecessor of a given Key in BST Video Explanation:

Algorithm to find the Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST):

  1. Return if root is NULL.
  2. If the root->data = key, then
    1. If the Left subtree exists,
      then the predecessor is the Rightmost node is the left subtree.
    2. If the Right subtree exists,
      then the Successor is the Left node is the Right subtree.
    3. Return.
  3. If root->data > key
    1. set successor = root.
    2. Recur on left Subtree.
  4. If root->data < key
    1. set Predecessor = root.
    2. Recur on Right Subtree.

The above algorithm also works even if the key does’t exist in the tree. In that case, it gives the range in which the number lies.

C++ code to find Inorder Successor and Predecessor of a given Key in BST :

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This functio is used to create and
initialise new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This funciton is used to Insert
 new values in BST*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*This function is used to find Inorder successor and 
Predecessor. NOTE that we pass the variables by 
reference */
void inorderPreSuc(node *root, node *&pre, node *&suc,int key)
{
   if(!root)
      return;
   /*Here the key is found*/	
   if(root->data==key)	
   {
      if(root->left)
      {
         /*Finding the Right most 
         node of left subtree*/
         
         node *temp=root->left;
         while(temp->right)
            temp=temp->right;
         pre=temp;
      }
      if(root->right)
      {
         /*Finding the left most 
         node of right subtree*/
         
         node *temp=root->right;
         while(temp->left)
            temp=temp->left;
         suc=temp;
      }
      return;
   }
   if(root->data > key)
   {
      suc=root;
      /*Recur on left subtree*/
      inorderPreSuc(root->left,pre,suc,key);
   }
   else
   {
      pre=root;
      /*Recur on right subtree*/
      inorderPreSuc(root->right,pre,suc,key);
   }
      
}

int main() {
   int key = 20;    //Key to be searched in BST
 
   /* Let us create following BST
              10
            /    \
           5     20
         /  \    /  \
        1    7  15   25 */
    node *root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);
 
 
    node *pre = NULL, *suc = NULL;
 
    inorderPreSuc(root, pre, suc, key);
    /*Checking the existence of predecessor and
    successor*/
    if (pre)
      cout << "Predecessor is " << pre->data << endl;
    else
      cout << "No Predecessor";
 
    if (suc)
      cout << "Successor is " << suc->data;
    else
      cout << "No Successor";
      
   return 0;
}

Output:

Predecessor is 15
Successor is 25

Time Complexity: O(H) where H is the height of the BST

Convert BST to Greater Sum Tree

Convert BST to Greater Sum Tree

This problem can also be stated as BST to Binary Tree Conversion with data of nodes as the sum of all greater elements.

This program/question can be seen as an extension/ modification of converting BST to Binary Tree with data of nodes as sum of all greater value nodes.

Convert BST to Greater Sum Tree Problem Statement:

Given a Binary Search Tree (BST), we need to add to each node, the sum of all greater values node.

Convert BST to Greater Sum Tree Example:

Input:    
              10
           /      \
          5        20
        /   \      /  \
       1     7    15   25 

Output after Modification:

              60
           /      \
         77        25
        /   \      /  \
      82    70    45   0

NOTE: This program will convert a BST into a Binary Tree with value of nodes as the sum of all greater elements.

Convert Binary Search Tree to Greater Sum Tree solution:

We use Reverse Inorder Traversal (recursion is called on right subtree first rather than left subtree) and maintain a variable to store the sum of nodes that have been traversed so far.

We then use this sum to modify the value of our present node, by first adding its value to the sum, and then replacing the value of the node with this sum.

C/C++ code for converting BST to Greater Sum Tree:

#include <bits/stdc++.h>
using namespace std;

/*Stucture of each node of the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*Function that allocates memory for
each new node and initialises it*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This functions is used to print the 
inOrder traversal of the array*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function inserts new nodes
into the Binary Search Tree*/
node *Insert(node *root,int key)
{
   if(!root)
      return newNode(key);
   if(key<root->data)	
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}

/*The function that uses reverse
inorder traversal to add the 
value of all greater elements*/
void RevInorderAdd(node *root,int &sum)
{
   if(!root)
      return;
      
   RevInorderAdd(root->right,sum);
   
   /*First add data to sum
   then replace the value in 
   node*/
   sum += root->data;
   root->data = sum - root->data;
   
   RevInorderAdd(root->left,sum);
}

/*utility function that hides
the actual implementation using
the above function*/
void AddGreater(node *root)
{
   int sum=0;
   RevInorderAdd(root,sum);
}

int main() {
   /* Let us create following BST
              10
            /    \
           5     20
         /  \    /  \
        1    7  15   25 */
    node *root = NULL;
    root = Insert(root, 10);
    Insert(root, 20);
    Insert(root, 25);
    Insert(root, 15);
    Insert(root, 5);
    Insert(root, 7);
    Insert(root, 1);
 
 	cout<<"Initial BST Inorder Travesal:\n";
    Inorder(root);
    cout<<endl;
    AddGreater(root);
 
    /*print inoder tarversal of 
    the modified BST*/
    cout<<"Modified BST Inorder Travesal:\n";
    Inorder(root);
    cout<<endl;
   return 0;
}

Output:

Initial BST Inorder Travesal:
1 5 7 10 15 20 25 
Modified BST Inorder Travesal:
82 77 70 60 45 25 0

Time Complexity: O(n) where n is number of nodes in the given BST.

Lowest Common Ancestor (LCA) in BST

Lowest Common Ancestor (LCA) in Binary Search Tree (BST)

Problem Statement LCA in a binary Search Tree (BST):

Given a binary search Tree(BST) and two numbers, we need to print the LCA of these two numbers numbers.
It can be assumed for simplicity that both these numbers exist in the given BST.

LCA of two numbers:

Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

Lowest Common Ancestor in a binary Search Tree (BST) Example:

        80
       /  \
      60   110
    /  \   /  \
   35  40  85 130

Case I:
If the two numbers are 85 and 40 then the output is 80, as it is the only node that has both of these numbers as descendants.

Case II:
If the two numbers are 110 and 130 then the output is 110, as per the definition of LCA given above.

Lowest Common Ancestor in a binary Search Tree (BST) Video Explanation:

Lowest Common Ancestor in a Binary Search Tree (BST) Solution:

Here we use recursion to find  the LCA of two number, there can be 3 cases that arise:

  1. If both the numbers are less than the root’s data, then LCA lies in the left subtree,and we recur on it.
    n1,n2<root’s data.
  2. If both the numbers are greater than the root’s data, then LCA lies in the right subtree,and we recur on it.
    n1,n2 > root’s data.
  3. If any of the above case doesnt match, then we have our LCA as this node, print the data of this node.This case is combination of these 2 sub-cases:
    1. If the root’s data lies between the two numbers.
      n1<root’s data<n2 or n2<root’s data<n1.
    2. If one of the number matches with the root’s data.
      root’s data == n1 or n2.

Lowest Common Ancestor (LCA) in a Binary Search Tree (BST) Solution in c++:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node of tree*/
struct node{
   int data;
   node *left;
   node *right;
};
 
/*This function creates and 
initialises new nodes*/
node * newNode(int data)
{
   node * temp = new node;
   temp->data=data;
   temp->right=temp->left=NULL;
   return temp;
}
 
/*This function inserts new nodes
int the Binary Search Tree*/
node * Insert(node * root, int data)
{
   if(!root)
      return newNode(data);
 
   if(data<root->data)	
      root->left=Insert(root->left,data);
   else
      root->right=Insert(root->right,data);
 
   return root;	
}

/*This function is used or print the
LCA of two numbers*/
void LCA(node *root,int n1,int n2)
{
   if(!root)
      return;
      
   /*If both numbers are smaller than
   the root's data, then LCA lies on 
   left subtree*/	
   if(root->data >n1 && root->data >n2 )	
      return LCA(root->left,n1,n2);
      
   /*If both numbers are greater than
   the root's data, then LCA lies on 
   right subtree */		
   else if(root->data <n1 && root->data <n2 )	
      return LCA(root->right,n1,n2);
   else
   {
      /*this case occurs when either of  
      the number matches with the root's 
      data or root's data lies in between 
      of the two numbers*/
      cout<<"The LCA of "<<n1<<" and "
         <<n2<<" is \n"<<root->data<<"\n";
      return;
   }	
}

 
/* Driver Program to test above functions */
int main()
{
    /* The following insertions create this
    	Binary Search Tree
              80
           /     \
          60      110
         /  \    /  \
       35   40  85   130 */
 
    node *root = NULL;
    root = Insert(root, 80);
    Insert(root, 110);
    Insert(root, 85);
    Insert(root, 130);
    Insert(root, 60);
    Insert(root, 40);
    Insert(root, 35);
 	
 	/*Finding LCA of n1 and n2*/
 	int n1=110,n2=130;
    LCA(root,n1,n2);
    LCA(root,85,40);
    return 0;
}

Output:

The LCA of 110 and 130 is 
110
The LCA of 85 and 40 is 
80

Time Complexity: O(H) where H is the height of the tree

Doubly Linked List Introduction

Doubly Linked List Introduction

This post will cover Introduction to Doubly Linked List  (DLL) , we recommend you go through Singly Linked List, to get a better understanding.

A Doubly Linked List (DLL) contains two pointers along with the data.
One of them points to the next node in the sequence, known as next pointer.
The other points back to the last node in the sequence, known as previous pointer.

Doubly Linked List Introduction Introduction to double linked list

Following is representation of a Doubly Linked List (DLL) node in C/C++ language:

Doubly Linked List Introduction Video Explanation:

We recommend you go through this video too, to get a complete understanding.

Doubly Linked list representation in c++:

Each node contains a data variable and 2 pointers 1 pointing to the previous node, and one pointing to the next node.

struct node
{
   int data;
   node *next;
   node *prev;
};

Advantages of Doubly Linked List over singly linked list:

  1. A Doubly Linked List (DLL) can be traversed in both forward and backward direction.
  2. The delete operation in Doubly Linked List (DLL) can be done in constant time: In singly linked list, to delete a node, pointer to the node before it is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.

Disadvantages of Doubly Linked List over singly linked list:

  1. The nodes require extra space for an previous pointer. It is possible to implement Doubly Linked List (DLL) with single pointer though.
  2. All operations require the extra pointer previous to be maintained and rewired along with the next pointer.

Linked List Introduction

Introduction to Linked List

Up until now, we used arrays to store linear data of similar types but arrays have following limitations:

  1. The size of the array must be known beforehand i.e. must know the upper limit on the number of elements in advance.
  2. Inserting a new element in an array of elements is more time taking, because space has to be created for the new elements by shifting old ones.
  3. Deletion is also time taking with arrays.

For example:
In a system if we maintain a sorted list of numbers in an array arr[ ].
arr[ ] = {10, 11, 15, 20, 40}
Consider we want to insert a new number, 12, then we have to move all elements after and including 15.
Similarly if we have to delete 15, we will have to shift everything after it to one place to the left.

This post is a can be used as Linked list tutorials for beginners, or by anyone who wants to clear the basics of Linked List.

Introduction to Linked List Video Explanation:

Linked List Representation in C/C++:

A linked list is made up of nodes.
Each node in a list consists of at least two parts:

  1. Data: The information we store in arrays as elements.
  2. Pointer to the next node: Address of the location of the next node of the linked list.

Linked List introduction

We use a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then value of head is NULL.

Linked List vs arraysAdvantages of Linked List over arrays:

  1. Dynamic size: As and when we need to, we can allocate memory and insert more nodes into the linked list.
  2. Ease of insertion/deletion: No shifting is required in insert, delete operations.

Drawbacks of Linked List:

  1. Linked list support sequential access. Starting at a given node, we can access only the node that it contains the address to/points to. Random access is not allowed. So we cannot do binary search with linked lists.
  2. Extra memory space for a pointer is required with each element of the list in comparison to arrays which only need space for data.
  3. Arrays have better cache locality. This causes a pretty big difference in performance.