Find distance between two nodes in Binary tree & BST.

#include <bits/stdc++.h>

using namespace std;



struct Node {

    struct Node* left, *right;

    int key;

};



struct Node* newNode(int key)

{

    struct Node* ptr = new Node;

    ptr->key = key;

    ptr->left = ptr->right = NULL;

    return ptr;

}



// Standard BST insert function

struct Node* insert(struct Node* root, int key)

{

    if (!root)

        root = newNode(key);

    else if (root->key > key)

        root->left = insert(root->left, key);

    else if (root->key < key)

        root->right = insert(root->right, key);

    return root;

}



int result=0;

Node *temp=NULL;



int findvikas(Node *root,int a,int b) {

    if(root==NULL) return 0;

    if(root->key==a || root->key==b){

        temp = root;

        return 1;

    }

 

    int l = findvikas(root->left, a, b);

    int r = findvikas(root->right, a, b);

    // cout<<l<<" "<<r<<" "<<root->key<<endl;

    if(l!=0 && r!=0){

        result = l+r;

        return l+r;

    }



    if(result!=0) return max(l,r);

    if(l!=0) return l+1;

    if(r!=0) return r+1;

    return 0;

}

int cal(Node *root, int b) {

    if(root==NULL) return -1;

    if(root->key==b)

     return 0;

 

    int l = cal(root->left,b);

    int r = cal(root->right,b);

    // cout<<l<<" "<<r<<"  "<<root->key<<endl;

    if(l!=-1) return l+1;

    else if(r!=-1) return r+1;

    else return -1;

}

int main()

{

    struct Node* root = NULL;

    root = insert(root, 20);

    insert(root, 10);

    insert(root, 5);

    insert(root, 15);

    insert(root, 30);

    insert(root, 25);

    insert(root, 35);

    insert(root, 1);

    int a = 5, b = 25;

 

    int res = findvikas(root,a,b);

 

    if(result==0) {

        if(temp->key == a) a = b;

        cout<<"distance "<<cal(temp,a)<<endl;

    } else

    cout<<"distance "<<result;

 

    return 0;

}

Java program to construct BST from given preorder traversal.

       
import java.io.*;
import java.util.*;

// Java program to construct BST from given preorder traversal

class Node {

    int data;
    Node left, right;

    Node(int d) {
        data = d;
        left = right = null;
    }
}

class BinaryTree {
   
    Node constructTree(int arr[], int start, int end) {
        Node root=null,head=null;
        if(end>0) {
            root=new Node(arr[start++]);
            head=root;
        } else return null;
        for(int i=start;i<=end;) {
            root=head;
            while(true) {
                if(root.data>=arr[i] && root.left!=null) {
                    root=root.left;
                } else if(root.data>=arr[i] && root.left==null){
                    root.left=new Node(arr[i++]);
                    break;
                }
                if(root.data<=arr[i] && root.right!=null) {
                    root=root.right;
                } else if(root.data<=arr[i] && root.right==null){
                    root.right=new Node(arr[i++]);
                    break;
                }
            }
        }
        return head;
    }
    
    void printInorder(Node node) {
        if (node == null) {
            return;
        }
        printInorder(node.left);
        System.out.print(node.data + " ");
        printInorder(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int pre[] = new int[]{10, 5, 1, 7, 40, 50};
        System.out.println("Inorder traversal of the constructed tree is ");
        Node root = tree.constructTree(pre,0,pre.length-1);
        tree.printInorder(root);
    }
}


       
 

Lowest Common Ancestor in a Binary Tree & Binary Search Tree.

       

import java.io.*;

import java.math.*;

import java.security.*;

import java.text.*;

import java.util.*;

import java.util.concurrent.*;

import java.util.regex.*;



class Node

{

    int data;

    Node left, right;



    Node(int item)

    {

        data = item;

        left = right = null;

    }

}



class BinaryTree

{

    Node root;

 

    /* Function to find LCA of n1 and n2. if tree is BST*/

    Node lca(Node node, int n1, int n2)

    {

        if (node == null)

            return null;



        if (node.data > n1 && node.data > n2)

            return lca(node.left, n1, n2);



        if (node.data < n1 && node.data < n2)

            return lca(node.right, n1, n2);



        return node;

    }

    /* Function to find LCA of n1 and n2. if tree is Binary Tree*/

    Node fun(Node head1,int val1, int val2) {

            if(head1==null)

                return null;

        if(head1.data==val1 || head1.data==val2)

            return head1;

        Node left = fun(head1.left,val1,val2);

        Node right = fun(head1.right,val1,val2);



        if(left!=null && left.data==val1 && right!=null && right.data==val2)

            return head1;

        if(left!=null && left.data==val2 &&  right!=null && right.data==val1)

            return head1;

        if(left!=null)

            return left;

        if(right!=null)

            return right;

        return null;

    }

    public static void main(String args[])

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(20);

        tree.root.left = new Node(8);

        tree.root.right = new Node(22);

        tree.root.left.left = new Node(4);

        tree.root.left.right = new Node(12);

        tree.root.left.right.left = new Node(10);

        tree.root.left.right.right = new Node(14);



        int n1 = 10, n2 = 14;

        Node t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);



        n1 = 14;

        n2 = 8;

        t = tree.lca(tree.root, n1, n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);



        n1 = 14;

        n2 = 20;

        // t = tree.lca(tree.root, n1, n2);

        t = tree.fun(tree.root,n1,n2);

        System.out.println("LCA of " + n1 + " and " + n2 + " is " + t.data);

     

    }

}


       
 

Apostek Java Hiring Challenge

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Iterator;

import java.util.Scanner;

import java.util.Set;

import java.util.TreeMap;

import java.util.TreeSet;

public class apostek {

static class index{

public long a,b;

public index(long a,long b){

this.a=a;

this.b=b;

}

@Override

public String toString() {

return "index [a=" + a + ", b=" + b + "]";

}

}

public static void insertSort(ArrayList<index> arr) {

int n = arr.size();

        for (int i=arr.size()-1; i<n; ++i)

        {

            index key = arr.get(i);

            int j = i-1;

            while (j>=0 && ( (arr.get(j).b-arr.get(j).a) > (key.b-key.a) || ((arr.get(j).b-arr.get(j).a) == (key.b-key.a) && arr.get(j).a<key.a)))

            {

                arr.add(j+1, arr.get(j));

                arr.remove(j+2);

                j = j-1;

            }

//            while(j>=0 && ((arr.get(j).b-arr.get(j).a) == (key.b-key.a) && arr.get(j).a<key.a))

//            {

//             arr.add(j+1, arr.get(j));

//                 arr.remove(j+2);

//                 j = j-1;

//            }

            arr.add(j+1, key);

            arr.remove(j+2);

        }

}

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);

long n,k;

String str;

n=sc.nextLong();

k=sc.nextLong();

sc.nextLine();

str=sc.nextLine();

int q;

// sc.nextInt()

q=sc.nextInt();

// sc.next();

ArrayList<index> arr =new ArrayList<index>();

arr.add(new index(1,n));

int i=0;

int Q=(int) k;

TreeMap<Long,Long> res = new TreeMap<Long, Long>();

while(Q-->0) {

// for(int w=0;w<arr.size();w++)

// System.out.println("array print "+arr.get(w));

index ind = arr.get(arr.size()-1);

// System.out.println("comming op "+ind);

index left = new index(0,0),right=new index(0,0);

arr.remove(ind);

long a,b,c;

// even

if((ind.a+ind.b)%2==1) {

c=(ind.a+ind.b)/2;

char t = str.charAt(i);

if(t=='L') {

res.put(c, (long) (i+1) );

if(c-1>=ind.a) {

left.a = ind.a;

left.b = c-1; 

} else left=null;

if(c+1<=ind.b) {

right.a = c+1;

right.b=ind.b;

} else right=null;

} else{

res.put(c+1, (long) (i+1) );

if(c>=ind.a) {

left.a = ind.a;

left.b = c; 

} else left=null;

if(c+2<=ind.b) {

right.a = c+2;

right.b=ind.b;

} else right=null;

}

} else{

// odd

c=(ind.a+ind.b)/2;

res.put(c, (long) (i+1));

if(c-1>=ind.a) {

left.a = ind.a;

left.b = c-1; 

} else left=null;

if(c+1<=ind.b) {

right.a = c+1;

right.b=ind.b;

} else right=null;

}

if(left!=null) {

arr.add(left);

insertSort(arr);

}

if(right!=null) {

arr.add(right);

insertSort(arr);

}

// System.out.println(left+" "+right);

// System.out.println("result "+ (c+1)+" "+(i+1));

i++;

}

while(q-->0) {

long a;

a=sc.nextLong();

if(res.containsKey(a)) {

System.out.println(res.get(a));

} else System.out.println(-1);

}

}

}

Longest Palindrome subsequences

Given a string S="abcdpcba".
The longest palindrome subsequences would be  "abcdcba".

Program:-

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main() {
    string st;
    cin>>st;
    int arr[st.size()][st.size()]={0};
    for(int i=0;i<st.size();i++)
        arr[i][i]=1;
    int len=2;
    while(len<=st.size()){
        for(int i=0;i<st.size()-len+1;i++)
        {
           int j=i+len-1;
            if(st[i]==st[j])
                arr[i][j]=arr[i+1][j-1]+2;
            else arr[i][j]=max(arr[i][j-1],arr[i+1][j]);
        }
        len++;
    }
    cout<<arr[0][st.size()-1]<<endl;
    vector< vector<string> >res;
    res.resize( st.size() , vector<string>( st.size()) );
    for(int i=0;i<st.size();i++)
        res[i][i]=st[i];
     len=2;
    while(len<=st.size()){
        for(int i=0;i<st.size()-len+1;i++)
        {
           int j=i+len-1;
            if(st[i]==st[j] && len==2)
               { string temp;temp+=st[i];
                     temp+=st[j];
                res[i][j]=temp;}
            else if(st[i]==st[j])
                res[i][j]=st[i]+res[i+1][j-1]+st[j];
            else {
                if(res[i][j-1].size() >res[i+1][j].size())
                    res[i][j]=res[i][j-1];
                else res[i][j]=res[i+1][j];
            }       
}
        len++;
    }
    cout<<res[0][st.size()-1]<<"\n";

  return 0;

}

HackeRank_weekofcode28_theValueofFriendship

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


int main() {
    int test;
    cin>>test;
    while(test--){
       unsigned long long int sum=0,temper=0,valuer=1;
            int n,m;
            cin>>n>>m;
            vector<long int>vec[n];
            for(int i1=0;i1<m;i1++){
                int a,b;
                cin>>a>>b;
                a--;b--;
                vec[a].push_back(b);
                vec[b].push_back(a);
             }      
        vector<vector<long int> >result;
        vector<bool>visited(n,false);
        for(int i1=0;i1<n;i1++)
            if(visited[i1]==false)
            {
                vector<long int>temp;
                vector<int>dist(n,-1);
                dist[i1]=0;//starting number is always 0..
                queue<int>que;
                temp.push_back(i1);
                que.push(i1);//starting vertex....
                visited[i1]=true;
                while(!que.empty()){
                    int index=que.front();que.pop();
                    for(int i=0;i<vec[index].size();i++){
                        if(dist[vec[index][i]]==-1 ){
                            dist[vec[index][i]]=dist[index]+1;
                            que.push(vec[index][i]);
                            temp.push_back(vec[index][i]);
                            visited[vec[index][i]]=true;
                        }
                    }
                }
            result.push_back(temp);
          }
       
         pair<long int,long int>pr[result.size()];
        for(int i=0;i<result.size();i++){
           long int pp=0,qq=0,rr=0;
            for(int j=0;j<result[i].size();j++){
                pp+=vec[result[i][j]].size();
             //   cout<<result[i][j]<<" ";
            }
           // cout<<endl;
            pr[i] = make_pair(pp,result[i].size());
        }
        sort(pr,pr+result.size());
        reverse(pr,pr+result.size());
        for(int i=0;i<result.size();i++){
            pr[i].first = pr[i].first / 2;
            //cout<<pr[i].first<<" "<<pr[i].second<<endl;
        }
       unsigned long long int temp1=0,temp2=0,glb=0,gman=0,presum=0,cnt=0;
        for(int i=0;i<result.size();i++)
        {
            int flg=0;presum=0;
            if(pr[i].first>0)
            {
                sum+=(pr[i].second-1)*gman;
            }  
            for(int j=1;j<=pr[i].first;j++){
                if(j<pr[i].second){
                   sum+=(j+1)*(j);
                    presum=j*(j+1);
                }
                else {
                    cnt++;
                    //sum+=presum;
                 }
            }
            gman+=presum;
                //cout<<sum<<"\n";
        }
        sum+=cnt*gman;
     
        cout<<sum<<endl;
      }
    return 0;
}

Swapping 3 variable without extra variable

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

int main() {
    int a,b,c;
    cin>>a>>b>>c;

    a=(a+c)-(c=a);
    b=(c+b)-(c=b);

    cout<<a<<" "<<b<<" "<<c;
    return 0;
}