Binary Tree operations

    public Node getBST(){
        BST bst = new BST();
        Node root= new Node(45);
        bst.insert(root, 20);
        bst.insert(root, 60);
        bst.insert(root, 21);
        bst.insert(root, 19);
        bst.insert(root, 55);
        bst.insert(root, 65);
        return root;
    }

    public Node getMirroredBST(){
        Node root= new Node(45);
        root.lc=new Node(60);
        root.rc=new Node(20);
        root.lc.lc= new Node(65);
        root.lc.rc = new Node(55);
        root.rc.lc= new Node(21);
        root.rc.rc= new Node (19);
        return root;
    }

    public Node getBSTSample(){
        Node root= new Node(4);
        root.lc=new Node(2);
        root.rc=new Node(6);
        root.lc.lc=new Node(1);
        root.lc.rc=new Node(3);
        root.rc.lc= new Node(5);
        root.rc.rc=new Node(6);
        return root;
    }

    /**
     * predefined we send min to integer min and  max to integer max
     *
     * when go to left then max will be root (update)
     * when go to right then min will be root
     *
     */
    public boolean isBST(Node root, int min, int max){
        if(root==null){return true;}
        if(root.data>min && root.data<max){
            return isBST(root.lc,min,root.data) && isBST(root.rc,root.data,max);
        }
            return false;
    }

    public boolean isMirrorTree(Node first,Node second){
        boolean isMirrored=false;
        //if both tree's root are null they are mirrored
        if(first==null && second==null) return true;
        //if node of one tree is null and corresponding other tree's node is not null
        // they are not mirrored
        else if((first==null && second!=null) || first!=null && second==null){
            return false;
        }
        else {
            // if both corresponding mirrored node are same
            if(first.data==second.data) {
                isMirrored=true;
            }
            else {
                return false;
            }
            // take one tree's left node and second's tree right node
            return isMirrored && isMirrorTree(first.lc, second.rc) && isMirrorTree(first.rc,second.lc);

        }
    }

    public boolean isBSTSame(Node first, Node second){
        boolean isSame=false;
        if(first==null && second==null) return true;
        else if((first==null && second!=null)||(first!=null && second==null)){
            return false;
        }
        else{
            if(first.data==second.data){
                isSame=true;
            }
            else return false;
            return isSame && isBSTSame(first.lc,second.lc) && isBSTSame(first.rc,second.rc);
        }
    }

    public void levelOrderTraversal(Node root){
        if(root!=null){
            if(nodeQueue.isEmpty()){
                nodeQueue.add(root);
            }
            if(root.lc!=null){
                nodeQueue.add(root.lc);
            }
            if(root.rc!=null){
                nodeQueue.add(root.rc);
            }
            levelOrderTraversal(root.lc);
            levelOrderTraversal(root.rc);
        }
    }

    public void zigZagTraversal(Node root,int level){
        if(root!=null){
            if(nodeQueue.isEmpty()){
                nodeQueue.add(root);
            }
            if(level%2==0){
                if(root.lc!=null){
                    nodeQueue.add(root.lc);
                }
                if (root.rc != null) {
                    nodeQueue.add(root.rc);
                }
                zigZagTraversal(root.lc,level+1);
                zigZagTraversal(root.rc,level+1);
            }
            else{
                if(root.rc!=null){
                    nodeQueue.add(root.rc);
                }
                if (root.lc != null) {
                    nodeQueue.add(root.lc);
                }
                zigZagTraversal(root.lc,level+1);
                zigZagTraversal(root.rc,level+1);
            }
        }
    }

    public boolean isSibling(Node root, int left,int right){
        if(root==null || root.lc==null || root.rc==null){
            return false;
        }
        else{
            return (left==root.lc.data && right==root.rc.data)|| (left==root.rc.data && right==root.lc.data)||
                    isSibling(root.lc,left, right) || isSibling(root.rc, left, right);
        }
    }
   
    public Node getCommonAncestorBST(Node root,int a, int b){
        if(root==null) return null;
        else{
            if(a==root.data||b==root.data) return root;
            else if(a<root.data && b<root.data){
                return    getCommonAncestorBST(root.lc, a, b);
            }
            else if(a>root.data && b>root.data){
                return getCommonAncestorBST(root.rc, a, b);
            }
            else if((a<root.data && b>root.data)|| (a>root.data && b<root.data)){
                return root;
            }
        }
        return null;
    }

    public Node getCommonAncestor(Node root, int a, int b){
        if (root == null) {
            return null;
        }
        if(root.data==a||root.data==b){
            return root;
        }
        Node left=getCommonAncestor(root.lc,a, b);
        Node right=getCommonAncestor(root.rc,a,b);
        if(left!=null && right!=null) return root;
        if(left==null) return right; else return left;
    }

    //finds distance from root to given data node. result distance is one less pathLength method returns
    public int pathLength(Node root, int data){
        if(root!=null){
            int pathLength=0;
            //
            if(root.data==data||(pathLength=pathLength(root.lc,data))>0||(pathLength=pathLength(root.rc,data))>0){
                return pathLength+1;
            }
            return 0;
        }
        return 0;
    }

    public int distanceBetweenTwoNode(Node root, int data1,int data2){
        if(root!=null){
            int data1DistanceFromRoot= pathLength(root,data1)-1;
            int data2DistanceFromRoot = pathLength(root, data2)-1;
            Node csaNode = getCommonAncestor(root, data1, data2);
            if(null==csaNode)return -1;
            int csaDistanceFromRoot= pathLength(root,csaNode.data)-1;
            int distance=data1DistanceFromRoot+data2DistanceFromRoot- 2* csaDistanceFromRoot;
            return distance;
        }
        return 0;
    }

    public void levelOrderTraversal(Node root,int level){
        if(root!=null && level>-1){
            if(level==0){
                System.out.print(root.data+" ");
            }
            else{
                levelOrderTraversal(root.lc, level-1);
                levelOrderTraversal(root.rc,level-1);
            }
        }
    }

   
    public void allLevelOrderTraversal(Node root){
        for(int i=0; i<getMaxDepth(root);i++){
            levelOrderTraversal(root, i);
            System.out.println("             --> Level:"+i);
        }
    }

    public int getMaxDepth(Node root){
        if(root==null){
            return 0;
        }
        else{
            int leftDepth=getMaxDepth(root.lc);
            int rightDepth=getMaxDepth(root.rc);
           
            if(leftDepth>rightDepth){
                return leftDepth+1;
            }
            else{
                return rightDepth+1;
            }
        }
    }

    public Node convertToDLLUtil(Node root){
        if(root==null) return root;
        if(root.lc!=null){
            Node left = convertToDLLUtil(root.lc);
            while(left.rc!=null) left=left.rc;
            left.rc=root;
            root.lc=left;
        }
        if(root.rc!=null){
            Node right = convertToDLLUtil(root.rc);
            while(right.lc!=null) right=right.lc;
            root.rc=right;
            right.lc=root;
        }
        return root;
    }

    public Node convertToDll(Node root){
        Node node = convertToDLLUtil(root);

        while (node.lc!=null){
            node=node.lc;
        }
        return node;
    }


    public void boundaryView(Node root){
        printLeftBoundary(root);
        printLeaves(root);
        printRightBoundary(root);
    }

    public void printLeftBoundary(Node root){
        if(root!=null){
            if(root.lc!=null){
                System.out.println(root.data);
                printLeftBoundary(root.lc);
            }
            else if(root.rc!=null){
                System.out.println(root.data);
                printLeftBoundary(root.rc);
            }
        }
    }
    public void printRightBoundary(Node root){
        if(root!=null){
            if(root.rc!=null){
                printRightBoundary(root.rc);
                System.out.println(root.data);
            }
            else if(root.rc!=null){
                printRightBoundary(root.lc);
                System.out.println(root.data);
            }
        }
    }
    public void printLeaves(Node root){
        if(root!=null){
            if(root.lc==null || root.rc==null){
                System.out.println(root.data);
            }
            printLeaves(root.lc);
            printLeaves(root.rc);
        }
    }

    public void connectToRightPointer(Node root){

        if(root!=null){
            Node tempLeft=root.lc;
            if(tempLeft!=null){
                if(root.rc!=null)
                tempLeft.next=root.rc;
                else{
                    Node dummy=root.next;
                    while(dummy.lc!=null||dummy.rc!=null){
                        dummy=dummy.next;
                    }
                    if(dummy.lc!=null)root.lc.next=dummy.lc;
                    else root.rc.next=dummy.rc;
                }

            }

            if(root.rc!=null && root.next!=null){
                root.rc.next=root.next.lc;
            }
            connectToRightPointer(root.lc);
            connectToRightPointer(root.rc);
        }
    }


    private List<Integer> treeViewList = new ArrayList<>();
    public void leftTreeView(Node root,int size){
        if(null!=root){
            if(size>=treeViewList.size()){
                treeViewList.add(root.data);
                System.out.println(root.data + " ");
                int tempSize=treeViewList.size();
                leftTreeView(root.lc,tempSize);
                leftTreeView(root.rc,tempSize);
            }
        }
    }


    public Node largestNumberNode(Node root) {
        if (root != null) {
            if (root.rc != null) {
                root = largestNumberNode(root.rc);
            } else {
                return root;
            }
        }
        return root;
    }

    public Node deleteNode(Node root, int num) {
        if (root != null) {
            if (num < root.data) {
                root.lc = deleteNode(root.lc, num);
            } else if (num > root.data) {
                root.rc = deleteNode(root.rc, num);
            } else if (num == root.data) {
                // case 1: if node has no child
                if (root.lc == null && root.rc == null) {
                    root = null;
                }
                // case 2: if node has 1 child
                else if (root.lc == null && root.rc != null) {
                    root = root.rc;
                    // return root;
                } else if (root.lc != null && root.rc == null) {
                    root = root.lc;
                    // return root;
                }
                // case 3: if node has two child
                else if (root.lc != null && root.rc != null) {
                    // get the largest of left side node and copy to root
                    Node largestNumberNode = largestNumberNode(root.lc);
                    root.data = largestNumberNode.data;
                    // now delete the largest node
                    root.lc = deleteNode(root.lc, largestNumberNode.data);

                    // we can also get the smallest of right side and copy to
                    // root and repeat the same proccess.
                }
            }
        }
        return root;
    }

/*
    public boolean isSubTree(Node parent, Node child){

    }
*/

    public Node search(Node root,int data){
        Node result=null;
        if(root!=null){
            if(data==root.data) result=root;
            else if(data>root.data){
                return search(root.rc,data);
            }
            else{
                return search(root.lc,data);
            }
            return result;
        }
        else return result;
    }


    public boolean isBSTBalanced(Node root){
        if(null==root) return true;
        int leftHeight= getMaxDepth(root.lc);
        int rightHeight= getMaxDepth(root.rc);
        if(Math.abs(leftHeight-rightHeight)>1){
            return false;
        }
        else{
            return isBSTBalanced(root.lc) && isBSTBalanced(root.rc);
        }
    }


/*
    public List<Node> combinationBST(int start, int end){
        List<Node> result= new ArrayList<>();
        for(int i=start;i<end;i++){
            if(start>end){
                result.add(null);
                return result;
            }

            List<Node> left= showMessage(start,)
        }

    }
*/


public boolean pathSum(Node root, int sum, List<Node> path){
    if(root==null) { return false;}
    if(sum-root.data==0){
        if(root.lc==null && root.rc==null){
            path.add(root);
            return true;
        }
    }
    else{
        if(pathSum(root.lc,sum-root.data,path)){
            path.add(root);
            return true;
        }
        if(pathSum(root.rc,sum-root.data,path)){
            path.add(root);
            return true;
        }
    }
    return false;
}

    public void insert(Node root, int data) {
        if (data <= root.data) {
            if (root.lc != null) {
                insert(root.lc, data);
            } else {
                root.lc = new Node(data);
            }
        } else if (data > root.data) {
            if(root.rc!=null){
                insert(root.rc,data);
            }
            else{
                root.rc=new Node(data);
            }
        }
    }

    //List<Integer> preOrder = new ArrayList<>();
    public void preOrder(Node root) {
        if (root != null) {
            System.out.println(root.data);
            //preOrder.add(root.data);
            preOrder(root.lc);
            preOrder(root.rc);
        }
    }

    public void inOrder(Node root){
        if(root!=null){
            inOrder(root.lc);
            System.out.print(root.data+" ");
            inOrder(root.rc);
        }
    }

    public void inOrderIteration(Node root){
        Stack<Node> stack = new Stack<Node>();
        if(root!=null)
        stack.push(root);

        while(!stack.isEmpty()) {
            if (root != null) {
                stack.push(root);//push element in stack
                root = root.lc;//move to left
            }
            else{
                root=stack.pop();//popping is done when left has ended
                System.out.print(root.data+ " ");//print root
                root=root.rc;//move to right
            }
        }
    }

    public void postOrder(Node root){
        if(root!=null){
            postOrder(root.lc);
            postOrder(root.rc);
            System.out.println(root.data+" ");
        }
    }

    /**
     * pass the storin    gArray size 2^(height of tree + 1) -1
     * to contain all values including leave node's child's null value
     *
     * pass initial parameter pos as 0
     */
    public void serialize(Node root,int pos,Integer [] storingArray){
        if(root==null){
            storingArray[pos]=-1;
        }
        else{
            storingArray[pos]=root.data;
            serialize(root.lc,pos*2+1,storingArray);
            serialize(root.rc,pos*2+2,storingArray);
        }
    }

    public void deserialize(Integer[] storingArray,int pos,Node node){
        if(storingArray[pos]==-1||pos>storingArray.length-1){
            node=null;
        }
        else{
            if(node==null) node = new Node(storingArray[pos]);
            deserialize(storingArray,pos*2+1,node.lc);
            deserialize(storingArray,pos*2+2,node.rc);
        }
    }


    Map<Integer,Integer> levelContainer= new TreeMap<>();
    public void topViewHelper(Node root,int level){
        if(root!=null){
            if(!levelContainer.containsKey(level)){
                levelContainer.put(level,root.data);
            }

                topViewHelper(root.lc,level-1);
                topViewHelper(root.rc,level+1);
        }
    }

    public void bottomViewHelper(Node root,int level){
        if(root!=null){
//            if(!levelContainer.containsKey(level)){
                levelContainer.put(level,root.data);
//            }

            bottomViewHelper(root.lc,level-1);
            bottomViewHelper(root.rc,level+1);
        }
    }


    public void topView(Node root){
        topViewHelper(root,0);
        for(int key:levelContainer.keySet()){
            System.out.println(levelContainer.get(key)+" ");
        }
    }

    public void bottomView(Node root){
        bottomViewHelper(root,0);
        for(int key:levelContainer.keySet()){
            System.out.println(levelContainer.get(key)+" ");
        }
    }

    public int diameter(Node root){
        if(root!=null){
            int leftHeight= getMaxDepth(root.lc);
            int rightHeight = getMaxDepth(root.rc);
            int leftDiameter = diameter(root.lc);
            int rightDiameter = diameter(root.rc);
            return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
        }
        return 0;
    }

    public Node sortedArrayToBST(int[] array,int low, int high){
            if(array.length<1 ||low==high)return null;
            int mid=(low+high)/2;
            Node root=new Node(array[mid]);
            root.lc=sortedArrayToBST(array,low,mid);
            root.rc=sortedArrayToBST(array,mid+1,high);
            return root;
    }

    public int getLevel(Node root,int a, int level){
        if(root==null) return -1;
        if(a==root.data) return level;
        else{
            int levelLeft=getLevel(root.lc,a,level+1);
            int levelRight=getLevel(root.rc,a,level+1);
            if(levelLeft!=-1) return levelLeft;
            else return levelRight;
        }

    }

    public boolean isCousin(Node root, int a, int b){
        if(root==null) return false;
        return getLevel(root,a,0)==getLevel(root,b,0) && !isSibling(root,a,b);
    }