# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max_diamter = 0
        self.dfs(root)
        return self.max_diamter

    def dfs(self, root):
        if not root:
            return -1

        left_height = self.dfs(root.left) + 1
        right_height = self.dfs(root.right) + 1
        combined_len = left_height + right_height

        if combined_len > self.max_diamter:
            self.max_diamter = combined_len

        return left_height if left_height > right_height else right_height

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        helper(root);

        return maxDiameter;
    }

    private int helper(TreeNode node) {
        if (node == null) return - 1;

        int leftHeight = helper(node.left) + 1;
        int rightHeight = helper(node.right) + 1;
        int len = leftHeight + rightHeight;
        if (len > maxDiameter) {
            maxDiameter = len;
        }

        return leftHeight > rightHeight ? leftHeight : rightHeight;
    }
}