Sunday, 10 February 2019

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

No comments:

Post a Comment

links for Data Structure

  1) 𝐁𝐞𝐜𝐨𝐦𝐞 𝐌𝐚𝐬𝐭𝐞𝐫 𝐢𝐧 𝐋𝐢𝐧𝐤𝐞𝐝 𝐋𝐢𝐬𝐭:  https://lnkd.in/gXQux4zj 2) 𝐀𝐥𝐥 𝐭𝐲𝐩𝐞𝐬 𝐨𝐟 𝐓𝐫𝐞𝐞 𝐓𝐫𝐚𝐯𝐞𝐫𝐬𝐚𝐥𝐬...