Recursion

Given the node of a binary tree `root`

, find the longest path between any two nodes in the tree, and return its length.
This is called the "diameter" of the tree.

The "length" of a path is defined as the total number of edges that the path contains.

**Example:**

$\notag \large \texttt{=> returns 6 (red path)}$

First Few Test Cases:

After doing some examples, you should realize the longest path is always shaped like the letter "n". This means the diameter go through whatever node has the tallest left and right trees:

Here's an equation for the diameter of the tree:

$\notag
\texttt{diameter} = \texttt{the biggest} \Big(\texttt{height(node.left)} + \texttt{height(node.right)} \Big) \\\texttt{of all nodes in the tree}$

That's just an equation - it's not recursive. We could try finding a recursive equation to solve the problem, but it's very difficult. So now what?

We might as well write a function for the height of a tree, since we clearly need to compute it no matter how we solve the problem.

1. Recursion

We can find the height of a node recursively:

This equation is recursive, which means it calls itself on literally every node in the tree, and finds its height. This means the recursion is already computing everything we need in order to compute the diameter. A clever idea is to "hijack" this recursion, and stick in a few lines of code so that it also computes the diameter, like this:

2. Base case

3. Code

We'll just keep a global variable `diameter`

which we update in the hijacking. It's the max `hL + hR`

we've seen so far, and at the very end it will be the answer. Here's the code:

Time Complexity $O(n)$

Space Complexity $O(n)$. `height`

calls itself until it reaches a null node, so it might get $n$ calls deep (the tree might be a flat line). This means the Call Stack might grow up to size $n$.

Mark as Completed: