Solution: Diameter of Binary Tree

Statement

Given a binary tree, you need to compute the length of the tree’s diameter. 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.

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

Constraints:

• The number of nodes in the tree is in the range $[1, 500]$.
• $-100 \leq$ Node.value $\leq 100$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach will be to pick one node, find the distance to every other node from the selected node, and keep track of the maximum value. Repeat this process with all the nodes of the tree. After this process, we’ll have the maximum possible distance between the two nodes. That will be the diameter of the tree.

The time complexity for the naive approach will be $O(n^2)$. As the tree grows, the time complexity increases.

Optimized approach using depth-first search

We need to calculate the height of the left and right subtrees and return the greater one to calculate the diameter. To calculate the height, we traverse the depth of the left and right subtrees. Therefore, the problem is a natural fit for the tree depth-first search pattern.

As seen in the example below, 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. Let’s explore both of these conditions.

Case 1: The longest path that passes through the root of the tree

We can use the height of the tree when the root node is included in the longest path. The height of a tree is the longest path from the root node to any leaf node in the tree. So, the height of a tree can be considered the longest path starting from the root. We can calculate the longest path of the complete tree as:

height(root -> left) + height(root -> right) + 1(root node itself)

The path starts from the deepest node in the left subtree (adding height(root -> left) to the diameter), passes through the root (adding 1 to the diameter), and ends at the deepest node in the right subtree (adding height(root -> right) to the diameter).

Let’s look at an example of this case in the illustration below: