# Diameter of Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/diameter-of-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/diameter-of-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Visa](https://scaleengineer.com/companies/visa), [Wix](https://scaleengineer.com/companies/wix), [Verkada](https://scaleengineer.com/companies/verkada), [Aurora](https://scaleengineer.com/companies/aurora)
---
## Problem
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:**

![](https://assets.glich.co/dsa/diameter-of-binary-tree/image0.jpg) 

**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, 104]`.
* `-100 <= Node.val <= 100`

# Approaches
## Brute Force Recursive Approach
This approach directly translates the definition of the diameter into a recursive algorithm. For each node, it considers the three possibilities for the longest path: it lies entirely in the left subtree, entirely in the right subtree, or it passes through the current node. The algorithm then recursively explores these possibilities. To find the length of the path passing through the current node, it calculates the heights of its left and right subtrees. This leads to a simple but inefficient solution because the height of the same subtree is calculated multiple times.
**Time:** O(N^2) in the worst case (skewed tree) and O(N log N) in the average case (balanced tree). This is because for each of the N nodes, we might traverse its entire subtree to calculate the height. · **Space:** O(N) in the worst case for a skewed tree, due to the recursion stack depth. O(log N) for a balanced tree.
**Pros:** Simple to understand and implement.; It's a direct translation of the problem's recursive definition.
**Cons:** Highly inefficient due to redundant computations.; The time complexity is O(N^2) in the worst-case scenario (a skewed tree), which can lead to a 'Time Limit Exceeded' error on large test cases.
### Explanation
The core idea is to break down the problem recursively. The function `diameterOfBinaryTree` computes the diameter for the tree rooted at the given node. At each node, it calculates the diameter that passes through it by summing the heights of its left and right subtrees. A separate `height` function is used for this, which itself is recursive. Then, it makes recursive calls to `diameterOfBinaryTree` on its left and right children to find the maximum diameter that might exist entirely within those subtrees. The final answer is the maximum of these three values. The major performance issue arises because the `height` function is called at each step of the `diameterOfBinaryTree` recursion, leading to overlapping subproblems being solved repeatedly.

```java
/**
 * 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 {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // Calculate the diameter passing through the current root.
        // The length of the path is height(left) + height(right).
        int rootDiameter = height(root.left) + height(root.right);

        // Recursively find the diameter in the left and right subtrees.
        int leftDiameter = diameterOfBinaryTree(root.left);
        int rightDiameter = diameterOfBinaryTree(root.right);

        // The result is the maximum of the three possibilities.
        return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
    }

    /**
     * Helper function to calculate the height of a tree (number of nodes on the longest path).
     */
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}
```
### Algorithm
- The main function `diameterOfBinaryTree(root)` is the entry point.
- If the current node `root` is `null`, the diameter is 0, so we return 0.
- For a non-null node, the diameter can be one of three possibilities:
  1. The diameter of the left subtree.
  2. The diameter of the right subtree.
  3. The length of the longest path that passes through the `root` node.
- We calculate the third possibility by finding the height of the left and right subtrees and summing them up. The path length is the number of edges, which equals `height(root.left) + height(root.right)`.
- The height is calculated by a separate helper function, `height(node)`, which recursively computes the longest path from the node to a leaf in terms of the number of nodes. `height(null)` is 0.
- We then recursively call `diameterOfBinaryTree` for the left and right children to find the diameters of the respective subtrees.
- The final result is the maximum of these three values.

## Optimized Depth-First Search (Single Pass)
This optimized approach avoids the redundant calculations of the brute-force method by using a single pass. It employs a Depth-First Search (DFS) traversal, specifically a post-order traversal. During the traversal, a helper function computes the height of each node's subtree. As the recursion unwinds, the function not only returns the height to its parent but also uses the heights of its left and right children to calculate the diameter passing through the current node. This diameter is then compared with a global maximum, which is updated if necessary. This way, both height calculation and diameter updates are done in a single, efficient O(N) pass.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H = N, leading to O(N) space. For a balanced tree, H = log N, leading to O(log N) space.
**Pros:** Optimal time complexity of O(N).; Solves the problem in a single pass over the tree, making it very efficient.; Space complexity is also efficient, depending on the tree's height.
**Cons:** Relies on a shared state (member variable or a passed-by-reference object) to track the maximum diameter, which can be considered less clean than a purely functional approach.
### Explanation
The key insight is that for any node, the two pieces of information we need are its height (to pass up to its parent) and the diameter that can be formed with it as the highest point (to update the global answer). A post-order traversal is perfect for this. We first recurse to the children. When the recursive calls return, they provide the height of the left and right subtrees. With these two values, we can calculate the diameter passing through the current node (`leftHeight + rightHeight`). We check if this is the largest diameter seen so far. Then, we calculate the height of the current node (`1 + max(leftHeight, rightHeight)`) and return it to the parent node. This process ensures that every node is visited only once, and its height is computed only once.

```java
/**
 * 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 {
    private int maxDiameter = 0;

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

    /**
     * This function returns the height of the tree rooted at 'node'
     * and updates the maxDiameter as a side effect.
     */
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively get the height of left and right subtrees
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);

        // The diameter passing through the current node is the sum of the heights
        // of its left and right subtrees.
        int currentDiameter = leftHeight + rightHeight;

        // Update the maximum diameter found so far.
        maxDiameter = Math.max(maxDiameter, currentDiameter);

        // The height of the tree rooted at the current node is 1 (for the current node)
        // plus the maximum height of its subtrees.
        return 1 + Math.max(leftHeight, rightHeight);
    }
}
```
### Algorithm
- Initialize a variable, `maxDiameter`, to store the maximum diameter found so far. This can be a class member or a mutable object passed through recursion.
- Create a recursive helper function, say `height(node)`, that does two things: calculates the height of the subtree rooted at `node` and updates `maxDiameter`.
- The `height(node)` function works as follows:
  - **Base Case:** If `node` is `null`, its height is 0. Return 0.
  - **Recursive Step:** Recursively call `height` for the left and right children to get their heights (`leftHeight` and `rightHeight`). This is a post-order traversal.
  - **Update Diameter:** After the recursive calls return, we have the heights of the subtrees. The diameter passing through the current `node` is `leftHeight + rightHeight`. We update our global `maxDiameter` with `max(maxDiameter, leftHeight + rightHeight)`.
  - **Return Height:** The function must return the height of the current subtree to its parent caller. The height is `1 + max(leftHeight, rightHeight)`.
- The main function `diameterOfBinaryTree` will initiate the process by calling `height(root)` and then return the final `maxDiameter`.

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { private int ans ; public int DiameterOfBinaryTree ( TreeNode root ) { dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int l = dfs ( root . left ); int r = dfs ( root . right ); ans = Math . Max ( ans , l + r ); return 1 + Math . Max ( l , r ); } }
```

### Java

```java
/** * 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 { private int ans ; public int diameterOfBinaryTree ( TreeNode root ) { ans = 0 ; dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = dfs ( root . left ); int right = dfs ( root . right ); ans = Math . max ( ans , left + right ); return 1 + Math . max ( left , right ); } }
```

### JavaScript

```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) {
    let ans = 0;
    const dfs = (root) => {
      if (!root) {
        return 0;
      }
      const [l, r] = [dfs(root.left), dfs(root.right)];
      ans = Math.max(ans, l + r);
      return 1 + Math.max(l, r);
    };
    dfs(root);
    return ans;
  };

```

### CPP

```cpp
/** * 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 { public: int ans ; int diameterOfBinaryTree ( TreeNode * root ) { ans = 0 ; dfs ( root ); return ans ; } int dfs ( TreeNode * root ) { if ( ! root ) return 0 ; int left = dfs ( root -> left ); int right = dfs ( root -> right ); ans = max ( ans , left + right ); return 1 + max ( left , right ); } };
```

### Python

```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 : def diameterOfBinaryTree ( self , root : TreeNode ) -> int : def dfs ( root ): if root is None : return 0 nonlocal ans left , right = dfs ( root . left ), dfs ( root . right ) ans = max ( ans , left + right ) return 1 + max ( left , right ) ans = 0 dfs ( root ) return ans
```