coding II - Neethahiremath/Wiki GitHub Wiki

package mix;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

public class NodeSubtreeRoot {

  static class NodeTree {

    public int id;
    public NodeTree left;
    public NodeTree right;

    public NodeTree(int id) {
      this.id = id;
      this.left = null;
      this.right = null;
    }
  }

  public static Vector<Integer> removeNode(NodeTree root, int nodeToBeRemoved) {

    Vector<Integer> result = new Vector<>();

    Queue<NodeTree> queue = new LinkedList<>();

    if (root == null) return null;

    if (nodeToBeRemoved == root.id) {
      addNonNullNodeToResultSet(root, result);
      return result;
    } else {

      result.add(root.id);
      //  queue.add(root);
      //  searchDeleteNode(nodeToBeRemoved, result, queue);

      // using preOrder Traversals
      // NodeTree nodeTree = searchDeleteNodeWithPreOrder(nodeToBeRemoved, root);

      // using InOrder
      // NodeTree nodeTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root);

      // using PostOrder
      NodeTree nodeTree = searchDeleteNodeWithPostOrder(nodeToBeRemoved, root);

      if (nodeTree != null) {
        addNonNullNodeToResultSet(nodeTree, result);
      }
    }
    return result;
  }

  private static void addNonNullNodeToResultSet(NodeTree root, Vector<Integer> result) {
    if (root.left != null) result.add(root.left.id);
    if (root.right != null) result.add(root.right.id);
  }

  // DFS Search preOrder
  private static NodeTree searchDeleteNodeWithPreOrder(int nodeToBeRemoved, NodeTree root) {

    if (root == null) return null;

    if (root.id == nodeToBeRemoved) return root;

    NodeTree leftTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root.left);
    if (leftTree == null) leftTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root.right);

    return leftTree;
  }

  // DFS Search InOrder
  private static NodeTree searchDeleteNodeWithInOrder(int nodeToBeRemoved, NodeTree root) {

    if (root == null) return null;

    NodeTree leftTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root.left);
    if (root.id == nodeToBeRemoved) return root;
    if (leftTree == null) leftTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root.right);

    return leftTree;
  }

  // DFS Search PostOrder
  private static NodeTree searchDeleteNodeWithPostOrder(int nodeToBeRemoved, NodeTree root) {

    if (root == null) return null;

    NodeTree leftTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root.left);

    if (leftTree == null) leftTree = searchDeleteNodeWithInOrder(nodeToBeRemoved, root.right);

    if (root.id == nodeToBeRemoved) return root;

    return leftTree;
  }

  private static void searchDeleteNode(
      int nodeToBeRemoved, Vector<Integer> result, Queue<NodeTree> queue) {
    while (!queue.isEmpty()) {
      NodeTree poll = queue.poll();
      if (poll.id == nodeToBeRemoved) {
        addNonNullNodeToResultSet(poll, result);
        break;
      }

      if (poll.left != null) queue.add(poll.left);
      if (poll.right != null) queue.add(poll.right);
    }
  }

  static void levelOrder(NodeTree root) {
    if (root == null) return;
    Queue<NodeTree> n = new LinkedList<>();
    n.add(root);
    while (!n.isEmpty()) {
      System.out.print(n.peek().id + " ");
      if (n.peek().left != null) n.add(n.peek().left);
      if (n.peek().right != null) n.add(n.peek().right);
      n.remove();
    }
  }

  public static void main(String[] args) {

    NodeTree nodeTree = new NodeTree(1);
    nodeTree.left = new NodeTree(2);
    nodeTree.right = new NodeTree(3);
    nodeTree.left.left = new NodeTree(4);
    nodeTree.left.right = new NodeTree(5);
    nodeTree.right.right = new NodeTree(6);
    nodeTree.right.right.left = new NodeTree(7);

    // levelOrder(nodeTree);

    Vector<Integer> res = removeNode(nodeTree, 2);

    System.out.print(res);
  }
}

swap(arr,0,arr.length-1-n);
swap(arr,arr.length-n,arr.length-1);
swap(arr,0,arr.length-1);

swap(arr,0,n-1);
swap(arr,n,arr.length-1);
swap(arr,0,arr.length-1);

static void swap(int[] arr,int low,int high){

    while(low<high){
        int temp=arr[low];
        arr[low]=arr[high];
        arr[high]=temp;
        low++;
        high--;
    }
}

private static int findMaxProduct(int[] A) {

    if(A.length==0){
        return 0;
    }

    int maxEnding=A[0], minEnding=A[0];
    int maxSoFar=A[0];

    int max=-1,min=-1;
    for(int i=1;i<A.length;i++){
        max=A[i]*maxEnding;
        min=A[i]*minEnding;
        maxEnding=Integer.max(A[i],Integer.max(max,min));
        minEnding=Integer.min(A[i],Integer.min(max,min));
        maxSoFar=Integer.max(maxEnding,maxSoFar);
    }

    return maxSoFar;
}

public static void main(String[] args) {
    int[] arr={8,3,1,2};

    int pivot=-1,maxEle=Integer.MIN_VALUE;

    for(int i=0;i<arr.length-1;i++){

        if(maxEle<arr[i]){
            maxEle=arr[i];
            pivot=i;
        }
    }

    int diff=arr.length-1-pivot;

    int sum=0;
    for(int i=0;i<arr.length;i++){
        sum+=arr[i]*((i+diff)%arr.length);
    }

    System.out.println(sum);

static void reverseWords(char[] ch){

    stringRev(ch,0,ch.length-1);


    int start=0,end;

    while(true){

        while(start<=ch.length-1 && ch[start]==' '){
            start++;
        }

        if(start>ch.length-1)
            break;

        end=start+1;
        while(end<=ch.length-1 && ch[end]!=' ')
            end++;

        stringRev(ch,start,end-1);
        start=end;
    }

}

static void stringRev(char[] str,int start,int end){


    if(str==null||str.length<2)
        return;

    while(start<end){
        char temp=str[start];
        str[start]=str[end];
        str[end]=temp;
        start++;
        end--;
    }
}