Consistent Hashing

https://www.acodersjourney.com/system-design-interview-consistent-hashing/

Diameter Of a binary Tree

public class DiameterOfTree {
   
    public static void main(String[] args) {
        Node node  = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.left.left = new Node(5);
        node.left.left.left.left = new Node(6);
        node.left.left.left.right  = new Node(7);
        node.left.left.right = new Node(8);
       
        //System.out.println(findHeight(node));
         System.out.println(diameter(node));
    }
   
    static void printInOrder(Node node) {
        if(null!=node) {
            printInOrder(node.left);
            System.out.println(node.value);
            printInOrder(node.right);
        }
    }
   
    static int diameter(Node node) {
        if(null==node) {
            return 0;
        }
        int lengthLeft,lengthRight;
       
        lengthLeft = findHeight(node.left);
        lengthRight = findHeight(node.right);
       
        int leftDiameter = diameter(node.left);
        int rightDiameetr = diameter(node.right);
       
        return Math.max(1+lengthLeft+lengthRight, Math.max(leftDiameter, rightDiameetr));
       
    }
   
    static int findHeight(Node node) {
        if(null==node) {
            return 0;
        }
        if(null==node.left && null==node.right) {
            return 1;
        }
        int left ,right ;
        if(null!=node.left) {
            left = findHeight(node.left);
        }else {
            left  = Integer.MIN_VALUE;
        }
       
        if(null!=node.right) {
            right = findHeight(node.right);
        }else {
            right = Integer.MIN_VALUE;
        }

        return 1+ Math.max(left, right) ;
    }
   
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}

output: 6

Check Mirror image of tree

public class CheckMirroImageInTree {
    public static void main(String[] args) {
        Node node  = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.left  =new Node(6);
        node.right.right = new Node(7);
       
        Node node2  = new Node(1);
        node2.left = new Node(3);
        node2.right = new Node(2);
        node2.left.left = new Node(7);
        node2.left.right = new Node(6);
        node2.right.left  =new Node(5);
        node2.right.right = new Node(4);
        System.out.println(checkMirror(node, node2));
    }
   
   
    static boolean checkMirror(Node node1,Node node2) {
        if(node1==null && node2 == null) {
            return true;
        }
        if(node1==null || node2==null) {
            return false;
        }
       
        if(node1.value == node2.value) {
            if(checkMirror(node1.left, node2.right) && checkMirror(node1.right, node2.left)) {
                return true;
            }
        }
        return false;
    }
   
   
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}

Delete a node from BST

public class DeleteFromBST {
    public static void main(String[] args) {
        int[] arr = {5,3,8,2,1,6,7,4,9};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
         Node node= removeNode(root, 5);
         printInorder(node);
    }
   
    static Node removeNode(Node root, int key) {
        if(null!=root) {
            if(key<root.value) {
                root.left = removeNode(root.left, key); //if key small then current node then recursion for left
            }else if(key>root.value) {
                root.right = removeNode(root.right, key);//if key small then current node then recursion for right
            }else {
                //check how many nodes after found current node
               
                //if only one child at key node or no child
                if(root.left==null) {
                    return root.right;   
                }else if(root.right==null) {
                    return root.left;
                }
               
                //if 2 child at key node
                //pass right
                root.value = findMin(root.right);//replace key node with min node
                root.right = removeNode(root.right, root.value);//remove duplicate min node from right as in previous step we hvae find min node from right
            }
           
        }
        return root;
    }
   
    static int findMin(Node node) {
        //find min till all left node end due to inorder successor rule
        int min = node.value;
        while(null!=node.left) {
            if(min>node.left.value) {
                min = node.left.value;
                node = node.left;
            }
        }
       
        return min;
    }
   
   
    static void printInorder(Node node) {
        if(null!=node) {
            printInorder(node.left);
            System.out.println(node.value);
            printInorder(node.right);
        }
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}

ref: https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

Boundary traversal of binary tree (Border Elements)

public class PrintBoundryOftree {

    public static void main(String[] args) {
        int[] arr = {10, 5, 4, 7, 15, 14, 17};
        Node root = null;
        for (int val : arr) {
            root = insertNode(root, val);
        }
        printInorder(root);

        System.out.println("\n*** print boundry***\n");
        System.out.println("**print left**");
        printLeftBoundry(root);
        System.out.println("\n**print right boundry**\n");
        printRightBoundry(root.right); //start from right  due to root already cover in left boundry
        System.out.println("\n**leaf boundry**\n");
        printLeafBoundry(root);
    }

    static void printLeftBoundry(Node node) {
        if (null != node) {
            if (null != node.left) {
                System.out.println(node.value);
                printLeftBoundry(node.left);
            } else if (null != node.right) {
                System.out.println(node.value);
                printLeftBoundry(node.right);
            }
        }
    }

    static void printRightBoundry(Node node) {
        if (null != node) {
            if (null != node.right) {
                System.out.println(node.value);
                printRightBoundry(node.right);
            } else if (null != node.left) {
                System.out.println(node.value);
                printRightBoundry(node.left);
            }
        }
    }

    static void printLeafBoundry(Node node) {
        if (null != node) {
            printLeafBoundry(node.left);
            if (null == node.left && null == node.right) {
                System.out.println(node.value);
            }
            printLeafBoundry(node.right);

        }
    }

    static void printInorder(Node root) {
        if (null != root) {
            printInorder(root.left);
            System.out.println(root.value);
            printInorder(root.right);
        } else {
            return;
        }

    }

    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }

    static class Node {

        Integer value;
        Node left;
        Node right;

        Node(Integer value) {
            this.value = value;
            left = right = null;
        }
    }
}

output:
**original**
4
5
7
10
14
15
17

*** print boundry***

**print left**
10
5

**print right**

15

**left**

4
7
14
17

Ref: https://www.youtube.com/watch?v=uemjIijtu2I

Print Diagonal of Binary tree and their sum

package tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class PrintDiagonalBinaryTree {
    public static void main(String[] args) {
       
        int[] arr = {10,5,4,7,15,14,17};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
         printInorder(root);
         System.out.println("\n*****print diagonl****\n");
         printDiagnol(root);
       
    }
    static void printInorder(Node root) {
        if(null!=root) {
            printInorder(root.left);
            System.out.println(root.value);
            printInorder(root.right);
        }else {
            return;
        }
       
    }
   
    static void printDiagnol(Node root) {
        Map<Integer, Integer> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        Node p=null;
        int count = 0;
        while(!queue.isEmpty()) {
            p = queue.remove();
            if(p==null) {
                count = count+1;
                queue.add(null);
                p = queue.remove();
                if(null==p) {
                    break;
                }
            }
            System.out.println("diagnol::"+count);
            while(null!=p) {
                System.out.println(p.value);
                if(map.containsKey(count)) {
                    map.put(count, map.get(count)+p.value);
                }else {
                    map.put(count, p.value);
                }
                if(null!=p.left) {
                    queue.add(p.left);
                }
                p = p.right;
            }
        }
        System.out.println("\n***print sum of each diagonal***\n");
        map.forEach((k,v)-> {
            System.out.println("diagonal ::"+k+" sum is::"+v);
        });
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
            } else {
                root.right = insertNode(root.right, value);
            }
            return root;
        }

    }
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}
output:
**origianl**
4
5
7
10
14
15
17

*****print diagonl****

diagnol::0
10
15
17
diagnol::1
5
7
diagnol::1
14
diagnol::2
4

***print sum of each diagonal***

diagonal ::0 sum is::42
diagonal ::1 sum is::26
diagonal ::2 sum is::4

Note: the reason behind adding null in queue to trigger end of a diagonal.
main logic: find diagonal using distance start from root d=0 and d=parent+1(for left sub tree) and d= parent(for right sub tree).


Ref: https://www.youtube.com/watch?v=e9ZGxH1y_PE

RecoverBinarySearchTree

public class RecoverBinarySearchTree {
    static Node temp1;
    static Node temp2;
    static Node previousNode=null,firstStartNode=null,LastEndNode=null;
    public static void main(String[] args) {
        int[] arr = {10,5,4,7,15,14,17};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
         System.out.println("*****************original***********");
         printInorder(root);
         temp1.value = 15; //replace from 5
         temp2.value = 5; //replace from 15
         System.out.println("*****************after replace***********");
         printInorder(root);
       
         System.out.println("*****************recover***********");
         findSegments(root);
         int val = firstStartNode.value;
         firstStartNode.value = LastEndNode.value;
         LastEndNode.value = val;
         printInorder(root);
       
       
    }
   
    static Node insertNode(Node root, Integer value) {
        Node newNode = new Node(value);
        if (root == null) {
            return newNode;
        } else {
            if (value <= root.value) {
                root.left = insertNode(root.left, value);
                if(root.left.value==5) {
                    temp1 = root.left;
                }
                if(root.left.value==15) {
                    temp2 = root.left;
                }
            } else {
                root.right = insertNode(root.right, value);
                if(root.right.value==5) {
                    temp1 = root.right;
                }
                if(root.right.value==15) {
                    temp2 = root.right;
                }
            }
           
            return root;
        }

    }
   
   
    static void findSegments(Node root) {
        if(null==root) {
            return;
        }
        findSegments(root.left);
        //logic
        if(previousNode!=null) {
            if(previousNode.value>root.value) {
                if(null==firstStartNode) {
                    firstStartNode = previousNode;
                }
                LastEndNode = root;
            }
        }
        previousNode = root;
        findSegments(root.right);
    }
   
    static void printInorder(Node root) {
        if(null!=root) {
            printInorder(root.left);
            System.out.println(root.value);
            printInorder(root.right);
        }else {
            return;
        }
       
    }
   
    static class Node{
        Integer value;
        Node left;
        Node right;
        Node(Integer value){
            this.value = value;
            left = right = null;
        }
    }
}
output:
*****************original***********
4
5
7
10
14
15
17
*****************after replace***********
4
15
7
10
14
5
17
*****************recover***********
4
5
7
10
14
15
17