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;
        }
    }
}

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

Get Minimum and maximum depth of Binary Tree

public class MinMaxDepthBT {
    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);
         }
       
       
          System.out.println(getMinLenthBT(root));
          System.out.println(getMaxLenthBT(root));
    }
   
    static void preorder(Node node) {
        if(null!=node) {
            System.out.println(node.value);
            preorder(node.left);
            preorder(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;
        }
    }
   
    public static int getMinLenthBT(Node root) {
        if(null==root) {
            return 0;
        }
        if(root.left==null && root.right==null) {
            return 1;
        }
        int left = root.left!=null ? getMinLenthBT(root.left) : Integer.MAX_VALUE;
        int right = root.right!=null ? getMinLenthBT(root.right) : Integer.MAX_VALUE;
        return 1+Math.min(left, right);
    }
   
    public static int getMaxLenthBT(Node root) {
        if(null==root) {
            return 0;
        }
        if(root.left==null && root.right==null) {
            return 1;
        }
        int left = root.left!=null ? getMaxLenthBT(root.left) : Integer.MIN_VALUE;
        int right = root.right!=null ? getMaxLenthBT(root.right) : Integer.MIN_VALUE;
        return 1+Math.max(left, right);
    }
}
output: min 3 and max 4

Create a balanced Binary Search Tree (BST) from a sorted array

public class CreateBST {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = createBST(arr, 0, arr.length-1);
         preorder(node);
    }
   
    static void preorder(Node node) {
        if(null!=node) {
            System.out.println(node.value);
            preorder(node.left);
            preorder(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;
        }
    }
   
    static Node createBST(int[] arr,int start,int end) {
        if(start>end) {
            return null;
        }
        int mid = (start+end)/2;
        Node node = new Node(arr[mid]);
        node.left = createBST(arr, start, mid-1);
        node.right = createBST(arr, mid+1, end);
        return node;
    }
   
    }

LowestCommonAncesstor

public class LowestCommonAncesstor {
   
    public static void main(String[] args) {
        int[] arr = {3,6,5,9,2,8};
         Node root = null;
         for(int val:arr) {
             root =  insertNode(root, val);
         }
       
         Node node = getLCA(root, 5, 8);//output 6
         System.out.println(node.value);
    }
   
    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;
        }
    }
   
    static Node getLCA(Node currentNode,int A,int B) {
        if(currentNode==null) {
            return null;
        }
        if(currentNode.value==A || currentNode.value==B) {
            return currentNode;
        }
        Node left = getLCA(currentNode.left, A, B);
        Node right = getLCA(currentNode.right, A, B);
        if(null!=left && null!=right) {
            return currentNode;
        }
        if(null==left) {
            return right;
        }else {
            return left;
        }
    }
   
}

Give an algorithm for printing the level order data in reverse order

For example, the output for the below tree should be: 4 5 6 7 2 3 1

public class PrintDataInReverseOrder {
    public static void main(String args[]) {
             Node rootNode = new Node("1");
             rootNode.left = new Node("2");
             rootNode.left.left = new Node("4");
             rootNode.left.right = new Node("5");
             rootNode.right = new Node("3");
             rootNode.right.right = new Node("7");
             rootNode.right.left = new Node("6");
           
             printInreverse(rootNode);
    }
   
    static void printInreverse(Node node) {
       
        Queue<Node> queue = new LinkedBlockingQueue<>();
        queue.add(node);
        Stack<String> stack = new Stack<>();
        while(!queue.isEmpty()) {
            Node node1 = queue.remove();
            stack.add(node1.value);
            if(null!=node1.right) {
                queue.add(node1.right);
            }
            if(null!=node1.left) {
                queue.add(node1.left);
            }
        }
       
        while(!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }
}

class BinayTree{
    static class Node{
        String value;
        Node left;
        Node right;
       
        Node(String val){
            value = val;
            left = right = null;
        }
       
    }
   
}

output: 4567231

Algorithm for finding the maximum element in binary tree without recursion java

public void findMax(Node node) {
        int root_val,max_val=0;
        if(null!=node) {
              Queue<Node> queue = new LinkedBlockingQueue<>();
              queue.add(node);
             
              while(!queue.isEmpty()) {
                  Node temp = queue.remove();
                  root_val = temp.value;
                  max_val = max_val<root_val ? root_val :max_val;
                 
                  if(null!=temp.left) {
                      queue.add(temp.left);
                  }
                  if(null!=temp.right) {
                      queue.add(temp.right);
                  }
              }
             
        }
       
        System.out.println(max_val);
    }

Algorithm for finding maximum element in binary tree java

public int findMax(Node node) {
        int maxVal = 0, root_val ,left_val,right_val;
       
        if(null!=node) {
            root_val = node.value;
            left_val = findMax(node.left);
            right_val = findMax(node.right);   
            maxVal = left_val>right_val ? left_val :right_val;
            maxVal = maxVal>root_val ? maxVal : root_val;
        }
       
       
        return maxVal;
    }

Algorithm for searching an element in binary tree java

public class SearchANodeUsingRecusrtion {
    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);
        SearchANodeUsingRecusrtion searchANodeUsingRecusrtion = new SearchANodeUsingRecusrtion();
        int output = searchANodeUsingRecusrtion.searchNode(node,6);
        if(output==1)
            System.out.println("found");
        else
            System.out.println("not found");
    }
   
    public int searchNode(Node node,int key) {
        if(null!=node) {
            if(node.value==key) {
                return 1;
            }else {
                int temp = searchNode(node.left,key);
                if(temp!=0) {
                    return 1;
                }else {
                 temp =    searchNode(node.right,key);
                 return temp;
                }
               
            }
       
        }else {
            return 0;
        }
       
    }
   
}


class BinayTree{
    static class Node{
        String value;
        Node left;
        Node right;
       
        Node(String val){
            value = val;
            left = right = null;
        }
       
    }
   
}

algorithm for searching an element in binary tree without recursion java

public class SearchNodewithoutRecursion {
    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);
        SearchNodewithoutRecursion searchANodeUsingRecusrsion = new SearchNodewithoutRecursion();
        int val = searchANodeUsingRecusrsion.findNode(node, 4);
        if(val==1)
            System.out.println("found");
        else
            System.out.println("not found");
    }
   
    public int findNode(Node node, int key) {
        if(null!=node) {
            Queue<Node> queue = new LinkedBlockingQueue<>();
            queue.add(node);
            while(!queue.isEmpty()) {
                Node temp = queue.remove();
                System.out.println(temp.value);
                if(temp.value == key) {
                    return 1;
                }
                if(null!=temp.left) {
                    queue.add(temp.left);
                }
                if(null!=temp.right) {
                    queue.add(temp.right);
                }
            }
        }
            return 0;
       
    }
}

class BinayTree{
    static class Node{
        String value;
        Node left;
        Node right;
       
        Node(String val){
            value = val;
            left = right = null;
        }
       
    }
   
}