Tree Diameter

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.


=> returns 6 (red path)\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:

diameter=the biggest(height(node.left)+height(node.right))of all nodes in 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)O(n)

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

Mark as Completed:
Test your code to get an output here!
Test your code to get an output here!