Check for Balanced Tree | Diameter of Binary Tree

I came across these 2 questions and found similarities in both of them.

Check for Balanced Tree | Practice | GeeksforGeeks

Practice | GeeksforGeeks | A computer science portal for geeks

Now, let's discuss the solution:

1. Check for a balanced tree:

Input:
       10
     /   \
    20   30 
  /   \
 40   60
Output: 1
Explanation: The max difference in height
of left subtree and right subtree is 1.
Hence balanced.

Here First we need to find the height of the binary tree for both part i.e. left tree and right tree for each node, if the difference between them is greater than 1 then it is not balanced tree, return false.

How to find the height of the binary tree? here is the code for the same.

public int height(Node root){
        if(root==null)
            return 0;
        return 1+ Math.max(height(root.left),height(root.right));
    }

To the above code send the root and it will give the maximum height of that node.

Here is the code for the same:

class Node
{
 int data;
 Node left,right;
 
 Node(int d)
 {
  data = d;
  left = right = null;  
 }
}
class Tree
{
    
    //Function to check whether a binary tree is balanced or not.
    boolean isBalanced(Node root)
    {
  if(root == null)
     return true;
     int leftHeight = height(root.left);
     int rightHeight = height(root.right);
     
     int val = (int)Math.abs(leftHeight-rightHeight);
    if(val<2 && isBalanced(root.left)&& isBalanced(root.right))
         return true;
         return false;
    }
    
    public int height(Node root){
        if(root==null)
            return 0;
        return 1+ Math.max(height(root.left),height(root.right));
    }
}

Here we are calling the height function to all nodes of the tree, and checking for the validations of it.

2. Diameter of binary tree

Here we need to find the maximum path between 2 nodes.

So here comes the solution similar to same, only few modification are there.

class Solution 
{
    //Function to return the diameter of a Binary Tree.
    int diameter(Node root) {
        if(root==null)
            return 0;
        return findMaxDiameter(root);
    }
    
    public int findMaxDiameter(Node root){
        if(root==null)
            return 0;
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        
        return Math.max(leftHeight+rightHeight+1,Math.max(findMaxDiameter(root.left),findMaxDiameter(root.right)));
        
    }
    
    public int height(Node root){
        if(root == null)
            return 0;
        return 1+ Math.max(height(root.left),height(root.right));
    }
}

The logic is the same for both, but here we are to check for Math.max for the same, and previously we are checking for the validations for the same.

So the difference is only 2 lines of code, the rest of the part is the same, and logic wise both are the same.

Thank you for reading!

Happy Coding!