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

     

    }

}