Diameter of Binary Tree

---

Diameter of Binary Tree: 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 [0, 10^4].
• -100 <= Node.val <= 100

---

Try this Problem on your own or check similar problems:

1. Diameter of N-ary Tree
2. Longest Path With Different Adjacent Characters

Solution:

Java

class Solution {
    private class Diameter{
        int value;
        Diameter(int value){
            this.value = value;
        }
    }
    public int diameterOfBinaryTree(TreeNode root) {
        Diameter maxDiameter = new Diameter(0);
        helper(root, maxDiameter);
        return maxDiameter.value;
    }
    private int helper(TreeNode root, Diameter maxDiameter){
        if(root == null) return 0;
        int left = helper(root.left, maxDiameter);
        int right = helper(root.right, maxDiameter);
        maxDiameter.value = Math.max(left + right, maxDiameter.value);
        return Math.max(left, right) + 1;
    }
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  const maxDiameter = { value: 0 };
  helper(root, maxDiameter);
  return maxDiameter.value;
};

function helper(root, maxDiameter) {
  if (root === null) return 0;
  const left = helper(root.left, maxDiameter);
  const right = helper(root.right, maxDiameter);
  maxDiameter.value = Math.max(left + right, maxDiameter.value);
  return Math.max(left, right) + 1;
}

Python

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

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        maxDiameter = self.Diameter(0)
        self.helper(root, maxDiameter)
        return maxDiameter.value

    def helper(self, root, maxDiameter):
        if root is None:
            return 0
        left = self.helper(root.left, maxDiameter)
        right = self.helper(root.right, maxDiameter)
        maxDiameter.value = max(left + right, maxDiameter.value)
        return max(left, right) + 1

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    struct Diameter {
        int value;
        Diameter(int value) : value(value) {}
    };

public:
    int diameterOfBinaryTree(TreeNode* root) {
        Diameter maxDiameter(0);
        helper(root, maxDiameter);
        return maxDiameter.value;
    }

private:
    int helper(TreeNode* root, Diameter& maxDiameter) {
        if (root == nullptr) return 0;
        int left = helper(root->left, maxDiameter);
        int right = helper(root->right, maxDiameter);
        maxDiameter.value = max(left + right, maxDiameter.value);
        return max(left, right) + 1;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

We use the same approach we used for calculating depth in Maximum Depth of Binary Tree, only this time we have one additional line maxDiameter.value = Math.max(left + right, maxDiameter.value);. So the diameter can either be the distance between left most leaf node and root if we don't have a right subtree or vice-versa, or height of left subtree plus the height of right subtree (think about two nodes that are most distant from each other appearing of course in different subtrees, on different sides of the root). We wrapped primitive type into class wrapper so we can pass it by reference to helper function and keep the best solution throughout recursion stack. You can however have a global variable or use an array of two elements (pair containing height and diameter).