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);

}

}

}