BinarySearchTree

import java.util.*;

public class BinarySearchTree {

    public static class Node {
        int data;
       Node left;
       Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        Node(int data)
        {
            this.data = data;
        }
    }

    public static Node construct(int[] arr ,int low ,int high) {
        if(low>high)
        {
            return null;
        }
        int mid = low + (high - low) / 2;
        int data = arr[mid];

        Node lc = construct(arr,low,mid-1);
        Node rc = construct(arr,mid+1,high);
        Node node = new Node(data,lc,rc);

        return node;
    }

    List<Integer> list = new ArrayList<>();
    public List<Integer> getAllElements(Node root1, Node root2) {

        if(root1 == null || root2 == null) {
            return list;
        }

        getAllElements(root1.left,root2.left);
        if(root1.data<root2.data) {
            list.add(root1.data);
            list.add(root2.data);
        }  else {
            list.add(root2.data);
            list.add(root1.data);
        }
        getAllElements(root1.right,root2.right);
        return list;

    }

    public static int size(Node node) {
        // write your code here

        if(node==null)
        {
            return 0;
        }
        int ls=size(node.left);
        int rs=size(node.right);
        int cs=ls+rs+1;
        return cs;
    }

    public static int sum(Node node)
    {
        if(node == null)
        {
            return 0;
        }
        int leftSum = sum(node.left);
        int rightSum = sum(node.right);
        int sum = node.data + leftSum+rightSum;
        return sum;
    }

    public static int max(Node node)
    {
        if(node == null)
        {
            return 0;
        }
        if(node.right!= null)
        {
            return max(node.right);
        }
        else {
            return node.data;
        }
    }

    public static int min(Node node)
    {
        if(node == null)
        {
            return 0;
        }
        if(node.left!= null)
        {
            return min(node.left);
        }
        else {
            return node.data;
        }
    }

    public static Node add(Node node,int data)
    {
        if(node == null)
        {
            return new Node(data,null,null);
        }
        if(data>node.data)
        {
          node.right = add(node.right,data);
        }
       else if(data<node.data)
        {
           node.left = add(node.left,data);
        }
       return node;
    }

    public static Node remove(Node node,int data)
    {
        if(node == null)
        {
            return null;
        }
        if(data>node.data)
        {
            node.right = remove(node.right,data);
        }
        else if(data<node.data)
        {
            node.left = remove(node.left,data);
        }
        else {
            if(node.left!= null && node.right!= null) {
                int lmax = max(node.left);
                node.data = lmax;
                node.left = remove(node.left,lmax);
                return node;
            }
           else if(node.left!= null) {
               return node.left;
            }
           else if(node.right!= null) {
             return node.right;
            }
           else {
               return null;
            }
        }
        return node;
    }

    static Node deleteNode(Node node, int key) {

        if(node == null) {
            return null;
        }
        if(key>node.data) {
            node.right = deleteNode(node.right,key);
        }
        else if(key<node.data) {
            node.left = deleteNode(node.left,key);
        }
        else {
            if(node.left!=null && node.right!= null) {
                Node temp = node.left;
                while (temp.right != null)
                    temp = temp.right;
                node.data = temp.data;
                node.left = deleteNode(node.left, temp.data);
            }
            else if(node.left!= null) {
                return node.left;
            }
            else if(node.right!= null) {
                return node.right;
            }
            else {
                return null;
            }
        }
        return node;

    }


    public static boolean find(Node node,int data)
    {
        if(node == null)
        {
            return false;
        }
        if(data>node.data)
        {
            return find(node.right,data);
        }
        else if(data<node.data)
        {
            return find(node.left, data);
        }
        else {
            return true;
        }
    }
static int sum = 0;
    public static void replaceSumOfLarger(Node node) {
        if(node == null)
        {
            return;
        }
        replaceSumOfLarger(node.right);
        int originalData = node.data;
        node.data = sum;
        sum = sum+originalData;
        replaceSumOfLarger(node.left);
    }

    public static void display(Node node) {
        if (node == null) {
            return;
        }

        String str = "";
        str += node.left == null ? "." : node.left.data + "";
        str += " <- " + node.data + " -> ";
        str += node.right == null ? "." : node.right.data + "";
        System.out.println(str);

        display(node.left);
        display(node.right);
    }

    static Node bstToGst(Node node) {

        if(node == null) {
            return null;
        }
        node.right = bstToGst(node.right);
        int od = node.data;
        node.data = sum+od;
        sum = sum+od;

        node.left = bstToGst(node.left);

        return node;

    }

    public static int lca(Node node ,int d1,int d2) {
        if(node == null)
        {
            return 0;
        }
        if(d1<node.data && d2<node.data) {
            return lca(node.left,d1,d2);
        }
        if(d1>node.data && d2>node.data) {
            return lca(node.right,d1,d2);
        }
        else {
            return node.data;
        }
    }
    public static void printInRange(Node node ,int d1,int d2) {
        if(node == null)
        {
            return;
        }
        if(d1<node.data && d2<node.data) {
            printInRange(node.left,d1,d2);
        }
      else if(d1>node.data && d2>node.data) {
            printInRange(node.right,d1,d2);
        }
        else {
            printInRange(node.left, d1, d2);
            System.out.println(node.data);
            printInRange(node.right, d1, d2);
        }
    }

    public static void travelAndPrintTarget(Node root,Node node ,int target)
    {
        if(node == null) {
            return;
        }
        travelAndPrintTarget(root,node.left,target);
        int comp = target-node.data;
        if(node.data<comp) {
            if(find(root,comp)) {
                System.out.println(node.data+" "+comp);
            }
        }
        travelAndPrintTarget(root,node.right,target);
    }

    public static void travelAndPrintTarget(Node node,int target)
    {
        ArrayList<Integer> list = new ArrayList<>();
         travelAndFill(node,list);
        if(node == null) {
            return;
        }
        int li = 0;
        int ri = list.size()-1;
        while (li<ri) {
            int left = list.get(li);
            int right = list.get(ri);
            if(left+right<target)
            {
                li++;
            }
            else if(left+right >target) {
                ri--;
            }
            else {
                System.out.println(left+" "+right);
                li++;
                ri--;
            }
        }
    }

    public static void travelAndFill(Node node, ArrayList<Integer> list) {
        if(node == null) {
            return;
        }
        travelAndFill(node.left,list);
        list.add(node.data);
        travelAndFill(node.right,list);
    }

    public List<Node> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }

        Map<String, List<Node>> memo = new HashMap<>();

        System.out.println(memo);

        List<Node>  res = generateTreesHelper(1, n, memo);

        memo.forEach((k,v)-> {
            System.out.print(k+" ");
            for(Node node : v) {
                levelOrder(node);
            }

        });
        System.out.println(memo);
        return res;
    }

    Node prev=null,first=null,second=null;
    void inorder(Node root){
        if(root==null)
            return;
        inorder(root.left);
        if(prev!=null && root.data<prev.data){
            if(first==null)
                first=prev;
            second=root;
        }
        prev=root;
        inorder(root.right);
    }
    //https://leetcode.com/problems/recover-binary-search-tree/submissions/1576928772/
    public void recoverTree(Node root) {
        if(root==null)
            return ;
        inorder(root);
        int temp=first.data;
        first.data=second.data;
        second.data=temp;
    }

    public static void levelOrder(Node node) {
        // write your code here
        Queue<Node> queue=new ArrayDeque<>();
        queue.add(node);
        while(queue.size()>0)
        {
            int size=queue.size();
            for(int i=0;i<size;i++) {
                node = queue.remove();
                System.out.print(node.data + " ");
                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            System.out.println();
        }
    }
//https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/5632202/video-2-solutions-with-o-n-2-and-o-n-time/
private int preorderIndex;
    private Map<Integer, Integer> mapping;
    public Node buildTree(int[] inorder, int[] postorder) {
        mapping = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            mapping.put(inorder[i], i);
        }
        preorderIndex = 0;
        return build1(inorder,postorder,0, inorder.length - 1);
    }

    //build tree from postorder and inorder
    private Node build1(int[] in,int[] post, int start, int end) {
        if (start > end) return null;

        int rootVal = post[post.length-1 - preorderIndex++];

        Node root = new Node(rootVal);
        if(start == end){
            return root;
        }
        int mid = mapping.get(rootVal);

        root.right = build1(in, post,mid + 1, end);
        root.left = build1(in, post,start, mid - 1);

        return root;
    }

    private Node build(int[] preorder, int start, int end) {
        if (start > end) return null;

        int rootVal = preorder[preorderIndex++];
        Node root = new Node(rootVal);
        int mid = mapping.get(rootVal);

        root.left = build(preorder, start, mid - 1);
        root.right = build(preorder, mid + 1, end);

        return root;
    }


    //https://leetcode.com/problems/unique-binary-search-trees/

    public int numTrees(int n) {
       // return solve(1,n).size();
        if(n<=1) {
            return 1;
        }
        int ans=0;

        for(int i = 1;i<=n;i++) {
            int lc = numTrees(i-1);
            int rc = numTrees(n-i);
            ans = ans+lc*rc;
        }

        return ans;
    }

    public List<Node> solve(int start,int end) {
        List<Node> trees = new ArrayList<>();
        if(start>end) {
            trees.add(null);
            return trees;
        }

        for(int rootValue = start;rootValue<=end;rootValue++) {
            List<Node> lc = solve(start,rootValue-1);
            List<Node> rc = solve(rootValue+1,end);

            System.out.println(trees);

            for(Node l:lc) {
                for(Node r:rc) {
                    Node root = new Node(rootValue);
                    root.left = l;
                    root.right = r;
                    trees.add(root);
                }
            }
        }

        return trees;

    }


    private List<Node> generateTreesHelper(int start, int end, Map<String, List<Node>> memo) {
        String key = start + "-" + end;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        List<Node> trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }

        for (int rootVal = start; rootVal <= end; rootVal++) {
            List<Node> leftTrees = generateTreesHelper(start, rootVal - 1, memo);
            List<Node> rightTrees = generateTreesHelper(rootVal + 1, end, memo);

            for (Node leftTree : leftTrees) {
                for (Node rightTree : rightTrees) {
                    Node root = new Node(rootVal);
                    root.left = leftTree;
                    root.right = rightTree;
                    trees.add(root);
                }
            }
        }

        memo.put(key, trees);
        return trees;
    }

    public Node sortedListToBST(LinkedList.Node head) {
        if(head==null)
            return null;
        if(head.next==null)
            return new Node(head.data);
        LinkedList.Node slow=head;
        LinkedList.Node fast=head;
        LinkedList.Node temp = null;
        while(fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            temp = slow;
            slow=slow.next;
        }

        if(temp!=null)
            temp.next = null; //break the link
        else
            head = null;

        Node res=new Node(slow.data);
      /*  LinkedList.Node righthalf=slow.next.next;
        slow.next=null;*/
        res.left=sortedListToBST(head);
        res.right=sortedListToBST(slow.next);
        return res;

    }

    private Node previous = null;
    public void flatten(Node root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = previous;
        root.left = null;
        previous = root;

    }

    //https://leetcode.com/problems/binary-tree-right-side-view/
    public List<Integer> rightSideView(Node root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    public void rightView(Node curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        System.out.println(curr.data);
        System.out.println("currDepth "+currDepth);
        System.out.println("result before"+result);
        System.out.println("result size "+result.size());
        if(currDepth == result.size()){

            result.add(curr.data);
        }

        System.out.println("result after"+result);

        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);

    }
    public static void main(String[] args) {
      //  int[] arr = {1,2,3, Integer.parseInt(null),5, Integer.parseInt(null),4};
       int[] arr = {12,75,37,50,62,25,87};
      //  int[] arr = {1,3,7};
        //int[] arr1 = {2,4,6};
       //int[] arr = {4,1,6,0,2,5,7, Integer.parseInt(null), Integer.parseInt(null), Integer.parseInt(null),3, Integer.parseInt(null), Integer.parseInt(null), Integer.parseInt(null),8};
        Node root = construct(arr,0,arr.length-1);
       // Node root1 = construct(arr1,0,arr1.length-1);
        BinarySearchTree bst = new BinarySearchTree();
       // display(root);
        //System.out.println(size(root));
       // System.out.println(sum(root));
      //  System.out.println(max(root));
      //  System.out.println(min(root));
      //  System.out.println(find(root,37));

      // Node newNode = add(root,40);
       // remove(root,75);
      //  System.out.println(sum(root));
      //  replaceSumOfLarger(root);
      //  System.out.println(sum(root));
       // printInRange(root,25,62);
     //   bstToGst(root);
      //  bst.recoverTree(root);
      //  bst.getAllElements(root,root1);
      //  deleteNode(root,25);
     //   travelAndPrintTarget(root,root,75);

       int[] preorder = {3,9,20,15,7};
       int[] inorder = {9,3,15,20,7};
       int[] postorder = {9,15,7,20,3};
       // bst.buildTree(inorder,postorder);
        LinkedList list=new LinkedList();
        list = list.insertNode(list, -10);
        list = list.insertNode(list, -3);
        list = list.insertNode(list, 0);
        list = list.insertNode(list, 5);
        list = list.insertNode(list, 9);

        bst.rightSideView(root);
        

    }



}