Saturday, 5 January 2019

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

No comments:

Post a Comment

links for Data Structure

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