Solution: Diameter of Binary Tree

Let's solve the Diameter of Binary Tree problem using the Tree Depth-first Search pattern.

We'll cover the following

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][1, 500].
  • −100≤-100 \leq Node.value ≤100\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(n2)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:

BT 1 1 2 2 1->2 3 3 1->3 4 4 2->4 5 5 2->5 6 6 3->6 7 7 5->7 8 8 5->8 9 9 6->9 10 10 9->10 11 11 9->11 12 12 10->12 13 13 10->13
The number of edges in the red part is the diameter of the tree

Case 2: The longest path that doesn’t pass through the root of the tree

In this case, the longest path can exist in either the left or right subtree. Since the root will not be a part of our path, we can consider the two subtrees to be new individual trees. The longest path for each of these trees needs to be calculated separately, and the longest one will be chosen.

BT 1 1 2 2 1->2 3 3 1->3 4 4 2->4 5 5 2->5 6 6 3->6 7 7 4->7 8 8 4->8 9 9 5->9 10 10 8->10 11 11 9->11 12 12 9->12 15 15 12->15 13 13 10->13 14 14 10->14
The number of edges in the red part is the diameter of the tree

We’ll calculate the diameter of the tree by using the diameterHelper() function. We need to calculate the left and right height of each node and update diameter = max(diameter, lh + rh). We’ll calculate this metric for each node and update the diameter. After traversing the whole tree, diameter will have the diameter of the tree.

Let’s look at the code for this solution below:

Note: The tree is provided as input in the form of a list containing the level order traversal

Solution.java
BinaryTree.java
TreeNode.java
import java.util.*;
class Pair {
    int diameter;
    int height;
    public Pair(int diameter, int height) {
      this.diameter = diameter;
      this.height = height;
    }
}
public class Solution {
  // Helper function to calculate diameter and height of a binary tree
  public static Pair diameterHelper(TreeNode<Integer> node) {
    if (node == null) {
      return new Pair(0, 0);
    } else {
      Pair lh = diameterHelper(node.left);
      Pair rh = diameterHelper(node.right);
      int height = Math.max(lh.height, rh.height) + 1;
      int diameter = Math.max(lh.diameter, Math.max(rh.diameter, lh.height + rh.height));
      return new Pair(diameter, height);
    }
  }
  // Function to find the diameter of a binary tree
  public static int diameterOfBinaryTree(TreeNode<Integer> root) {
    if (root == null)
      return 0;
    Pair pair = diameterHelper(root);
    return pair.diameter;
  }
  // Driver code
  public static void main(String args[]) {
    List<List<TreeNode<Integer>>> lists = Arrays.asList(
            Arrays.asList(new TreeNode<Integer>(2), new TreeNode<Integer>(1), new TreeNode<Integer>(4), new TreeNode<Integer>(3), new TreeNode<Integer>(5), new TreeNode<Integer>(6), new TreeNode<Integer>(7)),
            Arrays.asList(new TreeNode<Integer>(1), new TreeNode<Integer>(2), new TreeNode<Integer>(3), new TreeNode<Integer>(4), new TreeNode<Integer>(5), new TreeNode<Integer>(6), new TreeNode<Integer>(7), new TreeNode<Integer>(8), new TreeNode<Integer>(9)),
            Arrays.asList(new TreeNode<Integer>(45), new TreeNode<Integer>(32), new TreeNode<Integer>(23), new TreeNode<Integer>(21), new TreeNode<Integer>(19), new TreeNode<Integer>(18), new TreeNode<Integer>(1)),
            Arrays.asList(new TreeNode<Integer>(5), new TreeNode<Integer>(3), new TreeNode<Integer>(4), new TreeNode<Integer>(1), new TreeNode<Integer>(2), new TreeNode<Integer>(6), new TreeNode<Integer>(7), new TreeNode<Integer>(8), new TreeNode<Integer>(9)),
            Arrays.asList(new TreeNode<Integer>(9), new TreeNode<Integer>(7), null, null, new TreeNode<Integer>(1), new TreeNode<Integer>(8), new TreeNode<Integer>(10), null, new TreeNode<Integer>(12))
    );
    for (int i = 0; i < lists.size(); i++) {
      BinaryTree<Integer> t = new BinaryTree<Integer>(lists.get(i));
      System.out.println((i + 1) + ".\tBinary Tree");
      Print.displayTree(t.root);
      System.out.println(
          "\n\tDiameter of Tree: " + diameterOfBinaryTree(t.root));
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
Diameter of Binary Tree

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  • Start with the assumption that the diameter is 00.
  • Calculate the diameter of the left sub-tree and right sub-tree of the root node using the following recursive process:
    • At a leaf node, the diameter and height with respect to its children is 00 and 11, respectively.
    • For a non-leaf node, calculate the heights as well as the diameters of the left and right sub-trees. If the diameter passes through this node, then the diameter is the sum of the heights of the two sub-trees. Otherwise, it is the greater of the diameters of the two sub-trees.
  • Update the diameter as the greater of two values:
    • the sum of the heights of the left and right sub-trees,
    • the greater of the diameters of the two sub-trees.

Time complexity

The time complexity will be O(n)O(n) because each of the tree’s nodes gets visited once, where nn is the number of nodes in the tree.

Space complexity

The space complexity will be O(n)O(n) because the recursive stack can grow up to O(n)O(n), where nn is the number of nodes in the tree.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.