Level Order Traversal in a Binary Tree from Bottom to Top

    public void LevelOrderReverse()    {
        System.out.println(LevelOrderReverse(this));
    }
    private String LevelOrderReverse(BinarySearchTree T)    {
        StringBuffer sb = new StringBuffer();
        if(T!=null)    {
            Queue<BinarySearchTree> Q = new LinkedList<BinarySearchTree>();
            Stack<BinarySearchTree> S = new Stack<BinarySearchTree>();
            Q.add(T);
            while(Q.size() > 0)    {
                BinarySearchTree C = Q.remove();
                if (C.right != null)
                    Q.add(C.right);
                if (C.left != null)
                    Q.add(C.left);
                S.push(C);
            }
            while(S.size() > 0)
                sb.append(S.pop().data).append(", ");
        }
        return sb.toString();
    }

Bucket Sort

Amazon Question: Given an array with 3 distinct elements, sort the elements in O(n) complexity
Input: 1,3,1,2,3,1,2,2,3
Output: 1, 1, 1, 2, 2, 2, 3, 3, 3


import java.util.ArrayList;

public class BucketSort {
    ArrayList> bucket;
    private int count;
    public BucketSort(int unique_int_count) {
        this.count = unique_int_count;
        this.bucket = new ArrayList>();
        for(int i=0; i < this.count; i++) {
            bucket.add(new ArrayList());
    }
    public ArrayList Sort(ArrayList input)    {
        for(int c:input)    {
            if(c==1)    {
                bucket.get(0).add(c);
            }    else if(c==2)    {
                bucket.get(1).add(c);
            }    else    {
                bucket.get(2).add(c);
            }
        }
        ArrayList sorted_output = new ArrayList<>();
        for(int i=0; i < count; i++) {
            sorted_output.addAll(bucket.get(i));
        return sorted_output;
    }
    @Override
    protected void finalize() throws Throwable {
        bucket=null;
        super.finalize();
    }
}
//----------------------Main Method------------------------
    public static void main(String[] args) {
        BucketSort b = new BucketSort(3);
        ArrayList input = new ArrayList();
        input.add(1);
        input.add(3);
        input.add(1);
        input.add(2);
        input.add(3);
        input.add(1);
        input.add(2);
        input.add(2);
        input.add(3);
        System.out.println(b.Sort(input));
    }

Amazon Question: Print Last N nodes of Linked List in reverse

Given a singly linked list's head and an integer N, print last N nodes of the list in reverse order.
Example:
List = 1->2->3->4->5->6->7->8
N = 3
Output = 8, 7, 6,

    public void printRev(int count)    { // count = N
        temp = count;
// this here is the head node
        System.out.println(printRev(this, new StringBuffer()));
    }
    private int temp;
    private String printRev(LinkedList L, StringBuffer sb)    {
        if(L.next!=null)
            printRev(L.next, sb);
        if(temp>0)    {
            sb.append(L.data).append(", ");
            temp--;
        }
        return sb.toString();
    }

Tamil Kumari FM Talk about Birds

This is a talk about Birds which I gave 3 years ago in Kumari FM about Origin of Birds, Living Birds, Conservation of Birds.

Find if a Tree is a Binary Search Tree

public boolean isBinarySearchTree() {
return isBinarySearchTree(this, -99999, 99999);
}
public boolean isBinarySearchTree(BinarySearchTree T, int min, int max) {
if(T==null)return true;
if(T.data>min && T.data<max 
&& isBinarySearchTree(T.left, min, T.data) && isBinarySearchTree(T.right, T.data, max))
return true;
return false;
}

Find Maximum Sum of a SubArray

Example Input: -1,2,6,4,-4,-5,56,78,-2,9
Desired Output: 134 

    public int MaxSumOfSubArray(int... input)    {
        int size = input.length;
        int max = 0;
        boolean isIn = false;
        int current_sum = 0;
        int previous = -1;
        for(int i=0; i<size; i++)    {
            if(!isIn) current_sum = 0;
            if(input[i]>=0)    {
                isIn = true;
                current_sum = current_sum+input[i];
            }    else if(previous>=0 && max<current_sum)    {
                max = current_sum;
                isIn = false;
            }
            previous = input[i];
        }
        return max;
    }

Rotate an Array

    public int[] rotate(int count, int... input)    {
        for(int i=0; i&lt;count; i++)    {
            input = rotate(input);
        }
        return input;
    }
    private int[] rotate(int... input)    {
        int s =  input.length-1;
        int[] output = new int[input.length];
        for(int j=0; j < s; j++)    {
            output[j+1]=input[j];
        }
        output[0]=input[s];
        return output;
    }

Print all sub-set of a given set

    public HashSet<HashSet<Integer>> getAllSubset(HashSet<Integer> set)    {
        int[] superSet = getHashToIntArray(set);
        double max = Math.pow(2, superSet.length);
        HashSet<HashSet<Integer>> result = new HashSet<HashSet<Integer>>();
        for(int i=1; i<=max; i++)    {
            int n=i;
            HashSet<Integer> subset = new HashSet<Integer>();
            for(int j=0; j<superSet.length; j++)    {
                if(n%2==1)
                    subset.add(superSet[j]);
                n=n/2;
            }
            result.add(subset);
        }
        return result;
    }
   
    private int[] getHashToIntArray(HashSet<Integer> set)    {
        int[] result = new int[set.size()];
        int i=0;
        for(Integer n: set)    {
            result[i]=n;
            i++;
        }
        return result;
    }

Convert Numeric to Binary

With Recursion: 
    public StringBuffer convertToBinary(int n)    {
        if (n<2) return new StringBuffer().append(n);
        return new StringBuffer().insert(0, n%2).insert(0, convertToBinary(n/2));
    }

Without Recursion:
    public String convertToBinary(int n)    {
        StringBuffer result = new StringBuffer();
        while(n>0)    {
            result.insert(0, n%2);
            n=n/2;
        }
        return result.toString();
    }

Reversing Parts of a LinkedList

Initial LinkedList: 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 

Input: count = 3
Output: 3, 2, 1, 6, 5, 4, 9, 8, 7, 0, 

Input: count = 4
Output: 4, 3, 2, 1, 8, 7, 6, 5, 0, 9,

Input: count = 7
Output: 7, 6, 5, 4, 3, 2, 1, 0, 9, 8,


    public void compute(int count)    {
        LinkedList L = this;
        int i=0;
        StringBuffer sb = new StringBuffer();
        Stack<Integer> S = new Stack<Integer>();
        while(L!=null)    {
            if(i<count)    {
                S.push(L.data);
                L=L.next;
                i++;
            }    else    {
                while(!S.isEmpty())
                    sb.append(S.pop()).append(", ");
                i=0;
            }
        }
        while(!S.isEmpty())
            sb.append(S.pop()).append(", ");
        System.out.println(sb.toString());
    }

Inserting an Array of Elements in a Linked List

    public void insert(int... data)    {
        LinkedList L = this;
        while(L.next!=null)    {
            L=L.next;
        }
        int size=data.length;
        for(int i=0; i<size; i++)    {
            L.next=new LinkedList(data[i]);
            L=L.next;
        }
    }

Get All SubArray of a given Array

    public ArrayList<ArrayList<Integer>> getAllSubArray(int[] a)    {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for(int subarray_size=1; subarray_size<a.length; subarray_size++)    {
            ArrayList<Integer> newList = new ArrayList<Integer>();
            for(int i=0; i<a.length; i++)    {
                if((subarray_size+i)>a.length-1)
                    break;
                newList.add(a[i+subarray_size]);
                result.add(new ArrayList<>(newList));
            }
        }
        return result;
    }

Find if a Tree is a Mirror copy of another Tree

    public boolean isMirrorTrees(BinaryTree T1, BinaryTree T2)    {
        if(T1==null && T2==null)
            return true;
        if(T1.data!=T2.data)
            return false;
        if((T1==null && T2!=null) || (T2==null && T1!=null))
            return false;
        if(isMirrorTrees(T1.left, T2.right)
                && isMirrorTrees(T2.left, T1.right))
            return true;
        return false;
    }

Create a Mirror Copy of a Binary Tree

    public BinaryTree MirorCopyOfTree(BinaryTree T)    {
        BinaryTree newTree = new BinaryTree(T.data);
        if(T.left!=null)
            newTree.right=MirorCopyOfTree(T.left);
        if(T.right!=null)
            newTree.left=MirorCopyOfTree(T.right);
        return newTree;
    }

get Root to given Node path in a Binary Tree

    public void rootToNode(int data)    {
        getRootToNodePath(this, data, new StringBuffer(), false);
    }
    private void getRootToNodePath(BinarySearchTree T, int data, StringBuffer sb, boolean isFound)    {
        if(T!=null && !isFound)    {
            sb.append(T.data).append(", ");
            if(T.data==data)    {
                System.out.println(sb.toString());
                isFound = true;
                return;
            }    else    {
                getRootToNodePath(T.left, data, new StringBuffer(sb), isFound);
                getRootToNodePath(T.right, data, new StringBuffer(sb), isFound);
            }
        }
    }

Check if two Binary Tree are same

    public boolean isTreesSame(BinaryTree T1, BinaryTree T2)    {
        if(T1==null && T2==null)
            return true;
        if(T1==null || T2==null)
            return false;
        if(T1.data==T2.data
                && isTreesSame(T1.left, T2.left)
                && isTreesSame(T1.right, T2.right))
            return true;
        return false;
    }

Delete Node from Binary Search Tree

// Binary Search Tree full program is available here: link

    private BinarySearchTree ParentNode; //Parent Node of the node to delete

    private boolean LeftOrRightFlag; //Deleting node is Left from parent means true, else Right means false

    public void DeleteNode(int data)    {
        DeleteNode(this, data);
    }
    private void DeleteNode(BinarySearchTree T, int data)    {
        if(T==null) return;
        if(data==T.data)    {    //delete root note
            T.data=getMin(T.right).data;
            DeleteNode(T.right, T.data);
        }    else    {
            BinarySearchTree Current = findNode(T, data);
            if(Current.left==null && Current.right==null)
                if(LeftOrRightFlag)
                    ParentNode.left=null;
                else
                    ParentNode.right=null;
            else if(Current.left==null)
                if(LeftOrRightFlag)
                    ParentNode.left=Current.right;
                else
                    ParentNode.right=Current.right;
            else if(Current.right==null)
                if(LeftOrRightFlag)
                    ParentNode.left=Current.left;
                else
                    ParentNode.right=Current.left;
            else    {//Current node has both children
                Current.data=getMin(Current.right).data;
                DeleteNode(T.right, Current.data);
            }
        }
    }

    private BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }

    public BinarySearchTree findNode(BinarySearchTree T,int data)    {    //except root
        if(data==T.data)
            return T;
        else if(data<T.data)    {
            ParentNode=T;
            LeftOrRightFlag=true;
            return findNode(T.left, data);
        }    else    {
            ParentNode=T;
            LeftOrRightFlag=false;
            return findNode(T.right, data);
        }
    }

get InOrder sucessor of a given node in a BST

    private Stack<BinarySearchTree> S;
    public int inOrderSuccessor(int data)    {
        S = new Stack<BinarySearchTree>();
        BinarySearchTree Current = getNode(this, data);
        if(Current.right!=null)    {
            return getMin(Current.right).data;
        }    else    {
            BinarySearchTree parent = S.pop();
            if(parent.left==Current)
                return parent.data;
            else
                return S.pop().data;
        }
    }
    private BinarySearchTree getMin(BinarySearchTree T)    {
        while(T.left!=null)
            T=T.left;
        return T;
    }
    private BinarySearchTree getNode(BinarySearchTree T, int data)    {
        if(T==null)    return null;
        else if(data==T.data)        {
            return T;
        }
        else if(data<T.data) {
            S.add(T);
            return getNode(T.left, data);
        }
        else {
            S.add(T);
            return getNode(T.right, data);
        }
    }

is Binary Tree a Binary Search Tree

    public boolean isBinarySearchTree()    {
        return isBinaryTree(this, (-10^23), 10^23);
    }
    private boolean isBinarySearchTree(BinaryTree T, int min, int max)    {
        if(T==null) return true;
        if(T.data>min && T.data<max
                && isBinaryTree(T.left, min, T.data)
                && isBinaryTree(T.right, T.data, max))
            return true;
        return false;
    }

Insert Sorted Array into a Binary Search Tree with minimum height

public class BinarySearchTree {
    BinarySearchTree left, right;
    int data;
    public BinarySearchTree(int... SortedArrayOfdata) {
        int mid=SortedArrayOfdata.length/2;
        this.left=null;
        this.right=null;
        this.data=SortedArrayOfdata[mid];
        insertSortedArray(SortedArrayOfdata, 0, mid-1);
        insertSortedArray(SortedArrayOfdata, mid+1, SortedArrayOfdata.length-1);
    }
    private void insertSortedArray(int[] a, int startIndex, int endIndex)    {
        if(startIndex<=endIndex)    {
            int mid=(startIndex+endIndex)/2;
            insert(a[mid]); //Insert method is available here: link
            insertSortedArray(a, startIndex, mid-1);
            insertSortedArray(a, mid+1, endIndex);
        }
    }
}

Example Input:
BinarySearchTree BST = new BinarySearchTree(0,1,2,3,4,5,6,7,8,9,10,11,12,13);