Solving "Diameter of Binary Tree" Leet code Question

Intuition

We want to find the diameter of a binary tree, which is the length of the longest path between any two nodes. This path may or may not pass through the root.

Approach

We perform a depth-first traversal of the tree and calculate the height of each subtree. While calculating the height of each node, we also update the diameter if a longer path is found. The final result will be stored in the diameter variable.

Time complexity
O(n) - We visit each node once.

Space complexity
O(h) - Recursive call stack space, where h is the height of the tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }

    public int height(TreeNode node){

        if(node == null) {
            return 0;
        }

        int lh = height(node.left);
        int rh = height(node.right);
        diameter = Math.max(diameter,lh+rh);

        return 1 + Math.max(lh,rh);
    }
}

Happy coding,
shiva