543. Diameter of Binary Tree

Problem Description

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

• The number of nodes in the tree is in the range [1, 10⁴]
• -100 <= Node.val <= 100

Python Solution

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        
        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            
            left = height(node.left)
            right = height(node.right)
            
            # Update diameter if path through current node is longer
            self.diameter = max(self.diameter, left + right)
            
            # Return height of current subtree
            return 1 + max(left, right)
        
        height(root)
        return self.diameter

Java Solution

class Solution {
    private int diameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }
    
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = height(node.left);
        int right = height(node.right);
        
        // Update diameter if path through current node is longer
        diameter = Math.max(diameter, left + right);
        
        // Return height of current subtree
        return 1 + Math.max(left, right);
    }
}

C++ Solution

class Solution {
private:
    int diameter = 0;
    
    int height(TreeNode* node) {
        if (!node) {
            return 0;
        }
        
        int left = height(node->left);
        int right = height(node->right);
        
        // Update diameter if path through current node is longer
        diameter = max(diameter, left + right);
        
        // Return height of current subtree
        return 1 + max(left, right);
    }
    
public:
    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return diameter;
    }
};

JavaScript Solution

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function(root) {
    let diameter = 0;
    
    const height = (node) => {
        if (!node) {
            return 0;
        }
        
        const left = height(node.left);
        const right = height(node.right);
        
        // Update diameter if path through current node is longer
        diameter = Math.max(diameter, left + right);
        
        // Return height of current subtree
        return 1 + Math.max(left, right);
    };
    
    height(root);
    return diameter;
};

C# Solution

public class Solution {
    private int diameter = 0;
    
    public int DiameterOfBinaryTree(TreeNode root) {
        Height(root);
        return diameter;
    }
    
    private int Height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = Height(node.left);
        int right = Height(node.right);
        
        // Update diameter if path through current node is longer
        diameter = Math.Max(diameter, left + right);
        
        // Return height of current subtree
        return 1 + Math.Max(left, right);
    }
}