Java: Diameter of Binary Tree

Thought Process

To find the diameter of a binary tree, we can use a recursive approach. The diameter of a tree is the longest path between any two node, which may or may not pass through the root. We calculate the height of each subtree recursively and update the diameter as the maximum sum of the heights of the left and right subtrees. 

/**
 * 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;
    int height(TreeNode root){

        if(root==null)
            return 0;

        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        diameter = Math.max(diameter,leftHeight+rightHeight);
        return 1 + Math.max(leftHeight,rightHeight);
    }
    public int diameterOfBinaryTree(TreeNode root) {
        
        int x = height(root);
        return diameter;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case (a skewed tree), the space complexity is O(n).

Code copied!