optimized code for longestsubsequence for a String

String find_lcss(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return "";
        }
        int[][] table = new int[s1.length()][s2.length()];
        int maxLen = 0;
        int end_index = 0;

        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) != s2.charAt(j)) {
                    table[i][j] = 0;
                } else {
                    if (i == 0 || j == 0) {
                        table[i][j] = 1;
                    } else {
                        table[i][j] = table[i - 1][j - 1] + 1;
                    }
                }
                if (maxLen < table[i][j]) {
                    maxLen = table[i][j];
                    end_index = i;
                }
            }
        }
     
        StringBuilder res = new StringBuilder();
        for (int i = end_index + 1 - maxLen; i <= end_index ; i++) {
            res.append(s1.charAt(i));
        }
        return res.toString();
//System.out.println(end_index);
    }

WAP to find longest repeating subsequence

String longestSubstr(String str, String toCompare) {
        if (str == null || toCompare == null) {
            return null;
        }
        int[][] compareTable = new int[str.length()][toCompare.length()];
        int maxLen = 0;
        StringBuilder res = new StringBuilder();
        int m = 0, n = 0;
        for (; m < str.length(); m++) {
            for (; n < toCompare.length(); n++) {
                compareTable[m][n] = (str.charAt(m) != toCompare.charAt(n)) ? 0
                        : (((m == 0) || (n == 0)) ? 1
                        : compareTable[m - 1][n - 1] + 1);
                maxLen = (compareTable[m][n] > maxLen) ? compareTable[m][n]
                        : maxLen;
            }
        }
        for (int i = m + 1 - maxLen; i < m; i++) {
            res.append(str.charAt(i));
        }
        return res.toString();
    }

WAP for longest repeating subsequence

// return the longest repeated string in s

    public static String lrs(String s) {

        // form the N suffixes

        int N  = s.length();

        String[] suffixes = new String[N];

        for (int i = 0; i < N; i++) {

            suffixes[i] = s.substring(i, N);

        }

        // sort them

        Arrays.sort(suffixes);

        // find longest repeated substring by comparing adjacent sorted suffixes

        String lrs = "";

        for (int i = 0; i < N - 1; i++) {

            String x = lcp(suffixes[i], suffixes[i+1]);

            if (x.length() > lrs.length())

                lrs = x;

        }

        return lrs;

    }

heap sort optimized code

static void HeapSort(int[] arr) {
// TODO Auto-generated method stub
for(int i=0; i<arr.length;i++)
{
System.out.print(" "+arr[i]);
createHeap(arr,i);
}

System.out.println("     ");
System.out.println("heap generated");
for(int i=0; i<arr.length;i++)
{
System.out.print(" "+arr[i]);
}
for(int last=arr.length-1;last>0;)
{
int temp =arr[0];
arr[0]= arr[last];
arr[last--]=temp;
if(last>0)
fixHeap(arr,last);
}
}



private static void fixHeap(int[] arr,int last)
{
int currentIndex = 0;
boolean isHeap = false;

while (!isHeap) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
int maxIndex = currentIndex;

if (leftChildIndex <= last &&
arr[maxIndex] < arr[leftChildIndex]) {
maxIndex = leftChildIndex;
}

if (rightChildIndex <= last &&
arr[maxIndex] < arr[rightChildIndex]) {
maxIndex = rightChildIndex;
}

if (maxIndex != currentIndex) {
// Swap list[currentIndex] with list[maxIndex]
int temp = arr[currentIndex];
arr[currentIndex] = arr[maxIndex];
arr[maxIndex] = temp;
currentIndex = maxIndex;
} else {
isHeap = true;
}
}
}

private static void createHeap(int[] arr,int p) {
// TODO Auto-generated method stub
int parent=p;
while(parent> 0 && arr[parent]>arr[(parent-1)/2])
{
int temp=arr[parent];
arr[parent]=arr[(parent-1)/2];
arr[(parent-1)/2]=temp;

parent=(parent-1)/2;

}
}

find submatrix with non zero element for a given matrix

 static void findSubMatix(int[][] mat, int size) {
        int imax = 0, jmax = 0, res = 1;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int d = 0, r = 0, max = 1;
                while (max + i < size && j + max < size) {
                    if (mat[i + max][j] == 1 && mat[i][j + max] == 1) {
                        max++;
                    } else {
                        break;
                    }
                }
                int x = max - 1;
                d = i + max - 1;
                r = j + max - 1;
                if (mat[d][r] == 1) {
                    x--;
                    while (x > 0) {
                        if (mat[d - x][r] == 1 && mat[d][r - x] == 1) {
                            x--;
                        } else {
                            break;
                        }
                    }
                }
                if (x == 0 && res < max) {
                    res = max;
                    imax = i;
                    jmax = j;
                }
            }
        }
        System.out.println("\nsize :" + res + "(" + imax + "," + jmax + ")");
        for (int a = imax; a <= imax + res - 1; a++) {
            System.out.println();
            for (int b = jmax; b <= jmax+res-1; b++) {
                System.out.print(mat[a][b]+" , ");
            }
        }
    }

    static public void main(String[] args) {
        int[][] mat = {
            {1, 0, 1, 1, 1, 0, 0, 1},
            {1, 1, 1, 1, 0, 1, 1, 1},
            {1, 1, 1, 1, 1, 1, 1, 1},
            {0, 1, 1, 0, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 1},
            {1, 1, 1, 1, 0, 0, 0, 1},
            {1, 1, 1, 1, 1, 1, 1, 1},
            {1, 1, 1, 1, 1, 1, 1, 1}
        };
        findSubMatix(mat, 8);
    }

sudoko

public class Sudoko {

    public static void main(String[] args) {
        main();
    }

    static void main() {
        Square[][] board = new Square[9][9];
        initBoard(board);
        placeNumbers(board);
        printBoard(board);
    }

    static void initBoard(Square[][] board) {
        int[][] b = init();

        for (int r = 0; r < board.length; r++) {

            for (int c = 0; c < board.length; c++) {
                Square cell = new Square();
                board[r][c] = cell;
                board[r][c].val = b[r][c];
            }
        }
        setPossibles(board);
    }

    static void placeNumbers(Square[][] b) {

        while (hasEmptySpace(b)) {
            makeMove(findMove(b), b);
        }
    }

    static void printBoard(Square[][] b) {

        for (int r = 0; r < b.length; r++) {
            System.out.println(" ");

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val == 0) {
                    System.out.print("   ");
                } else {
                    System.out.print(" " + b[r][c].val + " ");
                }
            }
        }
    }

    static Coord findMove(Square[][] b) {
        Coord co = new Coord();

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val == 0 && unique(b[r][c].possibles)) {
                    co.row = r;
                    co.col = c;
                }
            }
        }
        return co;
    }

    static void makeMove(Coord c, Square[][] b) {
        int num = value(b[c.row][c.col].possibles);
        b[c.row][c.col].val = num;
        removeImpossibles(num, c.row, c.col, b);
    }

    static int[][] init() {
        int[][] b = {{1, 0, 6, 0, 9, 4, 0, 0, 0},
        {8, 0, 2, 1, 0, 0, 0, 3, 0},
        {0, 0, 0, 0, 5, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 3, 0, 6},
        {3, 6, 0, 0, 2, 0, 0, 8, 4},
        {2, 0, 7, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 6, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 8, 5, 0, 2},
        {0, 0, 0, 5, 3, 0, 9, 0, 7}};
        return b;
    }

    static boolean hasEmptySpace(Square[][] b) {

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val == 0) {
                    return true;
                }
            }
        }
        return false;
    }

    static boolean unique(boolean[] list) {
        int count = 0;

        for (int i = 1; i < list.length; i++) {

            if (list[i]) {
                count++;
            }
        }
        return count == 1;
    }

    static int value(boolean[] list) {
        assert (unique(list)) :
                "you need a look ahead, as this is a hard game";

        for (int i = 1; i < 10; i++) {

            if (list[i]) {
                return i;
            }
        }
        return 0;
    }

    static void setPossibles(Square[][] b) {

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {

                if (b[r][c].val != 0) {
                    removeImpossibles(b[r][c].val, r, c, b);
                }
            }
        }
    }

    static void removeImpossibles(int n, int r, int c, Square[][] b) {
        unSetInRow(n, r, b);
        unSetInCol(n, c, b);
        unSetInSquare(n, r, c, b);
    }

    static void unSetInRow(int n, int r, Square[][] b) {

        for (int i = 0; i < b.length; i++) {
            b[r][i].possibles[n] = false;
        }
    }

    static void unSetInCol(int n, int c, Square[][] b) {

        for (int i = 0; i < b.length; i++) {
            b[i][c].possibles[n] = false;
        }
    }

    static void unSetInSquare(int n, int r, int c, Square[][] s) {
        r = (r / 3) * 3;
        c = (c / 3) * 3;

        for (int i = r; i < r + 3; i++) {

            for (int j = c; j < c + 3; j++) {
                s[i][j].possibles[n] = false;
            }
        }
    }

    static void printSquare(Square s) {
        System.out.print("val = " + s.val);

        for (int i = 0; i < s.possibles.length; i++) {

            if (s.possibles[i]) {
                System.out.print("t ");
            } else {
                System.out.print("f ");
            }
        }
        System.out.println();
    }

    static void printBoardStructure(Square[][] b) {

        for (int r = 0; r < b.length; r++) {

            for (int c = 0; c < b.length; c++) {
                printSquare(b[r][c]);
            }
        }
    }
}

class Square {

    int val = 0;
    boolean[] possibles = {true, true, true, true, true, true, true, true, true, true};
}

class Coord {

    int row = 0;
    int col = 0;
}

WAP to find maximum possible pallendrome out of a given string

 static ArrayList<String> findMaxPalindrome(String str) {
        ArrayList<String> result = new ArrayList<String>();
        char[] ch = str.toCharArray();
        int ld = 0, rd = 0;
        for (int i = 0; i < ch.length - 1; i++) {
            if ((ch[i] == ch[i + 1]) || (i > 0 && ch[i - 1] == ch[i + 1])) {
                if (ch[i] == ch[i + 1]) {
                    ld = i - 1;
                    do{i++;}while(ch[i]==ch[i+1]);
                    rd = i + 1;
                } else if (i > 0) {
                    ld = i - 1;
                    rd = i + 1;
                }
                while (ld >= 0 && rd < ch.length) {
                    if (ch[ld] != ch[rd]) break;
                    ld--;   rd++;
                }
                if (rd - ld  > 3)
                    result.add(str.substring(ld+1, rd));
            }
        }
        return result;
    }

WAP to generate permutation of string

void permute(String str) {
        int length = str.length();
        boolean[] used = new boolean[length];
        StringBuilder out = new StringBuilder();
        char[] in = str.toCharArray();

        doPermute(in, out, used, length, 0);
    }

    static void doPermute(char[] in, StringBuilder out,
            boolean[] used, int length, int level) {
        if (level == length) {
            System.out.println(out.toString());
            ++count1;
            return;
        }

        for (int i = 0; i < length; ++i) {
            if (used[i]) {
                continue;
            }
            out.append(in[i]);
            used[i] = true;
            doPermute(in, out, used, length, level + 1);
            used[i] = false;
            out.setLength(out.length() - 1);
        }
    }

Anagram code

void doAnagram(StringBuilder prefix, StringBuilder suffix){
        if(suffix.length()==1){
            System.out.println(prefix.append(suffix));
            return;
        }
        for(int i=0;i < suffix.length();i++){
            String tempPre=prefix.toString();
            String tempSuf=suffix.toString();
            doAnagram(prefix.append(suffix.charAt(i)),new StringBuilder(suffix.substring(0, i)+suffix.substring(i+1, suffix.length())));
            prefix=new StringBuilder(tempPre);suffix=new StringBuilder(tempSuf);
        }
    }

optmized code to represent a num in byte

    static void getByte(int n) {

        int count = 0;
        while (n >= 1) {
            arr[count++] = (byte) (n % 2);
            n = n / 2;
        }
        while (count >= 0) {
            System.out.print(arr[count--] + " ");
        }
    }

divide a gievn array into two set of numbers such that the difference between the sum of those set is minmum ie do balance partioning

 
    public static void doBalanacePartition(int[] arr) {
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        int num = sum / 2;
        int k = num;
        while (!findNumSetBySum(arr, k)) {
            k++;
        }
        int j = num;
        while (!findNumBySum(arr, j)) {
            j--;
        }
    }


static boolean findNumBySum(int[] arr, int sum) {
        System.out.println("find all those two numbers whose sum is a given num : " + sum);
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            if (arr[i] + arr[j] > sum) {
                j--;
            } else if (arr[i] + arr[j] < sum) {
                i++;
            } else {
                System.out.println(arr[i] + " , " + arr[j]);
                i++;
                j--;
            }
        }
        return false;
    }

find closest pair

    static void findClosestPair(int[] arr) {
        int[] x = new int[]{1, 2, 4, 5, 6, 8, 9, 10, 12, 14};
        int[] y = new int[]{100, 98, 45, 63, 33, 96, 2, -10, -100, 400};
        float[] d = new float[10];
        float[] ang = new float[10];
        for (int i = 0; i < 10; i++) {
            d[i] = (float) Math.sqrt(x[i] * x[i] + y[i] * y[i]);
            ang[i] = y[i] / x[i];
        }
        for (int i = 1; i < d.length; i++) {
            float temp = d[i];
            int j = 0;
            while (j < i && d[i] > d[j]) {
                j++;
            }
            d[i] = d[j];
            d[j] = temp;
            float atemp = ang[i];
            ang[i] = ang[j];
            ang[j] = atemp;
        }
    }

present a number as sum of perfect squares minimum required

    static void findSquaredSet(int n) {
        System.out.println("present a givan num as sum of minimum required perfect squares: " + n);
        int j = (int) Math.floor(Math.sqrt(n));
        Stack stack = new Stack();
        int dif = n;
        while (j >= 1 && dif > 0) {
            //dif=dif-j*j;
            if (dif != 3 && dif != 8 && dif < j * j) {
                j--;
            } else {
                if (dif == 3) {
                    stack.push(1);
                    stack.push(1);
                    stack.push(1);
                    break;
                } else if (dif == 8) {
                    stack.push(2);
                    stack.push(2);
                    break;
                } else {
                    if (dif - j * j > 0) {
                        dif = dif - j * j;
                        stack.push(j);
                    }
                    j--;
                }
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + "^2+ ");
        }
        System.out.println("=" + n);
    }

optimized way to find /check a prime number

    static boolean isPrime(int n) {
        if (n == 1) {
            return false;
        }
        if (n == 2 || n == 3) {
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
        if (!(n % 6 == 1 || n % 6 == 5)) {
            return false;
        }
        int i = (int) Math.sqrt(n);
        for (int cnt = 5; cnt <= i; cnt++) {
            if (n % cnt == 0) {
                return false;
            }
        }
        return true;
    }

    static boolean prime(int n) {
        int i = (int) Math.sqrt(n);
        if (n % 2 == 0) {
            return false;
        }
        if (n % 3 == 0) {
            return false;
        }
        int j = 5;
        while (j <= i) {
            if (n % j == 0) {
                return false;
            }
            j++;
        }
        return true;
    }

in a given sorted array find allset of those numbers whose sun is equal to a given number

 static boolean findNumSetBySum(int[] arr, int sum) {
        int[] result = new int[100];
        boolean done = false;
        System.out.println("find set of num whose sum is a given num : " + sum);
        done= findNumSetBySum(arr, result, sum, 0, 0, false);
        return done;
    }

    static boolean findNumSetBySum(int[] arr, int[] result, int sum, int index, int i, boolean done) {
        if (sum == 0) {
            done = true;
            int j = 0;
            int n = 0;
            while (j < i) {
                if (result[j] != 0) {
                    System.out.print(result[j] + " , ");
                }
                j++;
            }
            System.out.println();
            return true;
        }
        if (done != true)
        {
            if ((sum > 0 && index == arr.length) || (sum < 0)) {
                return false;
            }
            if (sum > 0 && index < arr.length) {
                findNumSetBySum(arr, result, sum, index + 1, i, false);
                if (sum >= arr[index]) {
                    result[i] = arr[index];
                    findNumSetBySum(arr, result, sum - arr[index], index + 1, i + 1, false);
                }
            }
       //     return false;
        }
        return false;
    }

in a given sorted array find two number whose sum is equal to a given number

    static boolean findNumBySum(int[] arr, int sum) {
        System.out.println("find all those two numbers whose sum is a given num : " + sum);
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            if (arr[i] + arr[j] > sum) {
                j--;
            } else if (arr[i] + arr[j] < sum) {
                i++;
            } else {
                System.out.println(arr[i] + " , " + arr[j]);
                i++;
                j--;
            }
        }
        return false;
    }

in a given sorted array find two number whose difference is equal to a given number

  void findNumByDif(int[] arr, int dif) {
        System.out.println("find all possible set of number whose difference is a given num : " + dif);
        int i = 0, j = 1;
        while (i <= j && j < arr.length) {
            if (arr[i] + dif > arr[j]) {
                j++;
            } else if (dif + arr[i] == arr[j]) {
                System.out.println(arr[i] + " , " + arr[j]);
                i++;
                j++;
            } else {
                i++;
            }
        }
    }

one way search in BST (better than binary search)

newSearch(Node node, int data) {
        Node candidate = null;
        while (node != null) {
            if (data < node.data) {
                node = node.leftChild;                // { *** Try left subtree *** }
            } else {
                candidate = node;// { *** Save last rightward node *** }
                node = node.rightChild;// { *** Try right subtree *** }
            }
        }
        if (candidate != null && candidate.data == data) {
            return candidate;
        } else {
            return null;
        }
    }


here only one way comparision is done ie only less-than.

optmized code for printing max path length in a BST

public void OptimizedMaxPath() {
        OptimizedMaxPath(root);
    }

    private void OptimizedMaxPath(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        int count = 0, fMax = 0, sMax = 0;
        Node fNode = root, sNode = null; Node delNode = null;
        while (true) {
            while (node != null) {
                stack.push(node);
                 count++;
                node = node.leftChild;
               }
            if (stack.size() == 0) break;
                node = stack.pop();
                  if (fMax < count) {
                        sMax = fMax;
                        fMax = count;
                        fNode = node;
                    }
                    if (fMax > count && count > sMax) {
                        sMax = count;
                        if(fNode.parent!=sNode)
                        sNode = node;
                    }
                count--;
                node=node.rightChild;
      }
        System.out.print("\n nodes height" + fNode.data + " : " + sNode.data + "\n");
        Stack<Node> rStack = new Stack<Node>();
        while(true){
            if(fNode==root)break;
            if(fNode.parent!=null && fNode.parent.data > sNode.data)break;
            System.out.print(fNode.data+" : ");
            fNode=fNode.parent;
        }
        while (sNode!=fNode) {
            System.out.print(rStack.push(sNode) + " : ");
            sNode=sNode.parent;
        }
        while(!rStack.isEmpty())
            System.out.print(rStack.pop().data+" : ");
    }

print the longest path in BST

    public void printMaxPath() {
        int len = getHeight(root);
        int[] arr1 = new int[50];
        int[] arr2 = new int[2 * len - 1];
        int count = -1;
        if (root == null) {
            return;
        }
        System.out.print("\n print path  \n");
        //  ++count;
        //   arr1[count] = root.data;
        //   arr2[count] = root.data;
        //System.out.print(root.data+" : ");
        //printMaxPath(root.leftChild, arr1, arr2, count);
        printMaxPath(root, arr1, count);
        for (int i : arr1) {
            System.out.print(i + " : ");
        }
        System.out.print("\n");
        for (int i : arr2) {
            System.out.print(i + " : ");
        }
    }

    private void printMaxPath(Node node) {
        if (node.leftChild != null && node.rightChild != null) {
            int lh = getHeight(node.leftChild);
            int rh = getHeight(node.rightChild);
            if (lh > rh) {
                node = node.leftChild;
                System.out.print(node.data + " : ");
                printMaxPath(node);
            } else {
                node = node.rightChild;
                System.out.print(node.data + " : ");
                printMaxPath(node);
            }
        } else if (node.leftChild != null) {
            node = node.leftChild;
            System.out.print(node.data + " : ");
            printMaxPath(node);
        } else if (node.rightChild != null) {
            node = node.rightChild;
            System.out.print(node.data + " : ");
            printMaxPath(node);
        } else {
            return;
        }
    }

find a path having maximum sum of all node data in a given BST

    public int findMaxPath() {
        head = root;
        int maxPath = findMaxPath(root, 1);
        return maxPath;
    }

    public int findMaxPath(Node node, int max) {
        if (node == null) {
            return 0;
        }
        int lmax = getHeight(node.leftChild);
        int rmax = getHeight(node.rightChild);
        int path = lmax + rmax + 1;
        if (max < path) {
            max = path;
            head = node;
        }
        findMaxPath(node.leftChild, max);
        findMaxPath(node.rightChild, max);
        return max;
    }

compare two given BST are equal

public boolean isEqual(Node node) {
        return isEqual(root, node);
    }

    private boolean isEqual(Node b1, Node b2) {
        if (b1 == null && b2 == null) {
            return true;
        }
        if (b1 != null && b2 != null) {
            return ((b1.data == b2.data) && isEqual(b1.leftChild, b2.leftChild) && isEqual(b1.rightChild, b2.rightChild));
        }
        return false;
    }

convert a tree to list

    public Node TreeToList() {
        Node header = null;
        header = TreeToList(root);
        printList(header);
        return header;
    }

    private Node TreeToList(Node node) {
        if (node == null) {
            return (null);
        }
        Node header = null;
        Node current = null;
        Node temp = null;
        Stack<Node> stack = new Stack<Node>();
        while (true) {
            while (node != null) {
                stack.push(node);
                node = node.leftChild;
            }
            if (stack.isEmpty()) {
                break;
            }
            node = stack.pop();
            if (header == null) {
                header = current = node;
            } else {
                current.rightChild = node;
                node.leftChild = current;
                current = node;
            }
            node = node.rightChild;
        }
        current.rightChild = header;
        return header;
    }

print nodes of a BinaryTree in a Zig-zag way( left to right than right to left and so on)

 public void ZigZagPrint(Node node) {
        boolean LR = true;
        Stack<Node> pStack = new Stack<Node>();
        pStack.push(node);
        ZigZag(pStack, LR);
    }

    public void ZigZag(Stack<Node> Parent, boolean LR) {
        Stack<Node> Child = new Stack<Node>();
        if (Child.isEmpty() && Parent.isEmpty()) {
            return;
        }
        while (!Parent.isEmpty()) {
            Node temp = Parent.pop();
            System.out.print(temp.data + " , ");
            if (LR) {
                if (temp.leftChild != null) {
                    Child.push(temp.leftChild);
                }
                if (temp.rightChild != null) {
                    Child.push(temp.rightChild);
                }
            } else {
                if (temp.rightChild != null) {
                    Child.push(temp.rightChild);
                }
                if (temp.leftChild != null) {
                    Child.push(temp.leftChild);
                }
            }
        }
        Parent = Child;
        System.out.println();
        ZigZag(Parent, !LR);
    }

print a mirror of given Binary tree

Node MirrorTree(Node node) {
        if (node == null) {
            return node;
        }
        if (node.leftChild == null && node.rightChild == null) {
            return node;
        }
        if (node.leftChild != null && node.rightChild != null) {
            Node ltemp = node.leftChild;
            Node rtemp = node.rightChild;
            node.leftChild = rtemp;
            node.rightChild = ltemp;
            MirrorTree(node.leftChild);
            MirrorTree(node.rightChild);
        } else if (node.leftChild != null) {
            node.rightChild = node.leftChild;
            node.leftChild = null;
            MirrorTree(node.leftChild);
        } else {
            node.leftChild = node.rightChild;
            node.rightChild = null;
            MirrorTree(node.rightChild);
        }
        return node;
    }

delete a node from BST

 private boolean Delete(int data, Node node, Node grand, boolean isLeft) {
        if (node == null) {
            return false;
        }
        if (data < node.data) {
            return Delete(data, node.leftChild, node, true);
        } else if (data > node.data) {
            return Delete(data, node.rightChild, node, false);
        } else {
            if (node.leftChild != null && node.rightChild != null) {
                if (isLeft == true) {
                    Node temp = grand.leftChild;
                    grand.leftChild = findReplacement(node.rightChild);
                    node = grand.leftChild;
                    node.leftChild = temp.leftChild;
                    node.rightChild = temp.rightChild;
                } else {
                    Node temp = grand.rightChild;
                    grand.rightChild = findReplacement(node.rightChild);
                    node = grand.leftChild;
                    node.leftChild = temp.leftChild;
                    node.rightChild = temp.rightChild;
                }
            } else {
                if (node.leftChild == null && node.rightChild == null) {
                    if (isLeft == true) {
                        grand.leftChild = null;
                    } else {
                        grand.rightChild = null;
                    }
                } else if (node.rightChild == null) {
                    if (isLeft == true) {
                        grand.leftChild = node.leftChild;
                    } else {
                        grand.rightChild = node.leftChild;
                    }
                } else if (node.leftChild == null) {
                    if (isLeft == true) {
                        grand.leftChild = node.rightChild;
                    } else {
                        grand.rightChild = node.rightChild;
                    }
                }
            }
            return true;
        }

    }

    Node findReplacement(Node node) {
        Node parent = null;
        Node result = null;
        while (node.leftChild != null) {
            parent = node;
            node = node.leftChild;
            result = node;
        }
        if (node.rightChild != null) {
            parent.leftChild = node.rightChild;
        } else {
            if (parent != null) {
                parent.leftChild = null;
            } else {
                result = node;
            }
        }
        return result;
    }

find the path from root to leaf having sum of all node data equal to given number

    public void hasPathSum(int data) {
        int[] arr = new int[100];
        int pathSum = -1;
        hasPathSum(arr, root, pathSum, data);
    }

    private void hasPathSum(int[] arr, Node node, int pathSum, int num) {
        if (node == null) {
            return;
        }
        arr[++pathSum] = node.data;
        num -= node.data;
        if (num == 0 && (node.leftChild == null && node.rightChild == null)) {
            System.out.print("\n has path sum");
            printPath(arr, pathSum);
        }
        if (node.leftChild != null && num >= node.leftChild.data) {
            hasPathSum(arr, node.leftChild, pathSum, num);
        }
        if (node.rightChild != null && num >= node.rightChild.data) {
            hasPathSum(arr, node.rightChild, pathSum, num);
        }
    }

print all distinct paths form root to all leaf of BST

    public void printAllPaths() {
        int[] arr = new int[100];
        int pathSum = -1;
        printAllPaths(arr, root, pathSum);
    }

    private void printAllPaths(int[] arr, Node node, int pathSum) {
        arr[++pathSum] = node.data;
        if (node.leftChild == null && node.rightChild == null) {
            printPath(arr, pathSum);
        }
        if (node.leftChild != null) {
            printAllPaths(arr, node.leftChild, pathSum);
        }
        if (node.rightChild != null) {
            printAllPaths(arr, node.rightChild, pathSum);
        }
    }

    private void printPath(int[] arr, int pathSum) {
        int data = 0;
        System.out.println();
        for (; data <= pathSum; data++) {
            System.out.print(arr[data] + " , ");
        }
    }

find min and max node of a BST

public int findMin(Node node) {
        if (node == null) {
            return 100;
        }
        while (node.leftChild != null) {
            node = node.leftChild;
        }
        return node.data;
    }

    public int findMax(Node node) {
        if (node == null) {
            return -100;
        }
        while (node.rightChild != null) {
            node = node.rightChild;
        }
        return node.data;
    }

find whether tree is BinarySerachTree or not

    public boolean isBst() {
        return isBst(root);
    }

    private boolean isBst(Node node) {
        if (node == null) {
            return true;
        }
        if (node.leftChild == null && node.rightChild == null) {
            return true;
        }
        return (node.data > findMax(node.leftChild) && node.data < findMin(node.rightChild) && isBst(node.leftChild) && isBst(node.rightChild));
    }

find height of a tree

    public int getHeight() {
        if (root == null) {
            return 0;
        }
        if (root.leftChild == null && root.rightChild == null) {
            return 1;
        }
        return getHeight(root);
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return (Math.max(getHeight(node.leftChild), getHeight(node.rightChild)) + 1);
    }

level order traversal - iterative

void iterative_levelOrder(Node node) {
        Queue<Node> queue = new LinkedList();
        queue.offer(node);
        Node mark = new Node('&');
        queue.offer(mark);
        while (true) {
            Node delNode = queue.poll();
            if (queue.isEmpty() || delNode == null) {
                break;
            }
            if (delNode != mark) {
                System.out.print(delNode.data + " , ");
                if (delNode.leftChild != null) {
                    queue.offer(delNode.leftChild);
                }
                if (delNode.rightChild != null) {
                    queue.offer(delNode.rightChild);
                }
            } else {
                System.out.println();
                queue.offer(mark);
            }
        }
    }

postorder traversal (iterative)

 void iterative_postOrder(Node node) {
        Stack<Node> stack = new Stack<Node>();
        Node delNode = null;
        int maxSize=0,size=0;
        while (true) {
            while (node != null) {
                stack.push(node);
                size++;
                node = node.leftChild;
                if(node==null){
                    if(size > maxSize)
                        size=maxSize;
                }
            }
            if (stack.size() == 0) {
                break;
            }
            if (stack.peek().rightChild == null || delNode == stack.peek().rightChild) {
                delNode = stack.pop();
                size--;
                System.out.print(delNode.data + " , ");
            } else {
                node = stack.peek().rightChild;
            }
//            if (stack.peek().rightChild != null && delNode != stack.peek().rightChild) {
//                node = stack.peek().rightChild;
//            } else {
//                delNode = stack.pop();
//                System.out.print(delNode.data + " , ");
//                if (!stack.isEmpty() && delNode != stack.peek().rightChild) {
//                    node = stack.peek().rightChild;
//                }
//            }
        }
        System.out.print("\n postorder: max stackSize ="+maxSize);
    }

preorder traversal (iterative)

  void iterative_preOrder(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        int maxSize=0,size=0;
        while (true) {
            while (node != null) {
                System.out.print(node.data + " , ");
                stack.push(node);
                size++;
                node = node.leftChild;
                if(node==null){
                    if(maxSize< size)
                        maxSize=size;
                }
            }
            if (stack.size() == 0) {
                break;
            }
            node = stack.pop();
            size--;
            node = node.rightChild;
        }
        System.out.print("\n preorder :max stackSize ="+maxSize);
    }

inorder traversal (iterative)

 public void iterative_inOrder() {
        iterative_inOrder(root);
    }

    private void iterative_inOrder(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        int maxSize=0,size=0;
        while (true) {
            while (node != null) {
                stack.push(node);
                size++;
                node = node.leftChild;
                if(size > maxSize)
                    maxSize=size;
            }
            if (stack.size() == 0) {
                break;
            }
            node = stack.pop();
            size--;
            System.out.print(node.data + " , ");
            node = node.rightChild;
        }
        System.out.print("\ninorder :max stackSize ="+maxSize);
    }

what a binarySearchtree

public class BinaryTree {

    Node head;

    Node root;

    Node senital = new Node('&');

    Node candidate = null;

    public BinaryTree() {

        root = null;

    // root.leftChild=null;

    //  root.rightChild=null;

    }

    public void insert(int data) {

        if (root == null) {

            root = new Node(data);

            return;

        }

        insert(root, data);

    }

    private void insert(Node node, int data) {

        if (node == null) {

            node = new Node(data);

            // node.leftChild = senital;

            //node.rightChild = senital;

            //   System.out.println(data);

            return;

        }

        if (data < node.data) {

            if (node.leftChild == null) {

                node.leftChild = new Node(data);

                node.leftChild.parent = node;

            } else {

                insert(node.leftChild, data);

            }

        } else {

            if (node.rightChild == null) {

                node.rightChild = new Node(data);

                node.rightChild.parent = node;

            } else {

                insert(node.rightChild, data);

            }

        }

    }

}