This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given a binary tree, you need to compute 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.

**Example:**

Given a binary tree

1 / \ 2 3 / \ 4 5

Return **3**, which is the length of the path [4,2,1,3] or [5,2,1,3].

**Note:**
The length of path between two nodes is represented by the number of edges between them.

b'

\n\n

\n#### Approach #1: Depth-First Search [Accepted]

\n

\n

'
\n

**Intuition**

Any path can be written as two *arrows* (in different directions) from some node, where an arrow is a path that starts at some node and only travels down to child nodes.

If we knew the maximum length arrows `L, R`

for each child, then the best path touches `L + R + 1`

nodes.

**Algorithm**

Let\'s calculate the depth of a node in the usual way: max(depth of node.left, depth of node.right) + 1. While we do, a path "through" this node uses 1 + (depth of node.left) + (depth of node.right) nodes. Let\'s search each node and remember the highest number of nodes used in some path. The desired length is 1 minus this number.

\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: . We visit every node once.

\n \n - \n
Space Complexity: , the size of our implicit call stack during our depth-first search.

\n \n

\n

Analysis written by: @awice.

\n