Given a binary tree, write an efficient algorithm to compute the diameter of it. A binary tree diameter equals the total number of nodes on the longest path between any two leaves in it.

The following figure shows two binary trees with diameters 6 and 5, respectively (nodes highlighted in blue). The binary tree diameter shown on the left side passes through the root node, while the diameter of the binary tree shown on the right side does not pass through the root node.

 
Diameter of a Binary Tree

Practice this problem

A simple solution would be to calculate the left and right subtree’s height for each node in the tree. The maximum node path that passes through a node will have a value one more than the sum of the height of its left and right subtree. Finally, the diameter is maximum among all maximum node paths for every node in the tree. The time complexity of this solution is O(n2) as there are n nodes in the tree, and for every node, we are calculating the height of its left and right subtree that takes O(n) time.

 
We can solve this problem in linear time by doing a postorder traversal on the tree. Instead of calculating the height of the left and the right subtree for every node in the tree, get the height in constant time. The idea is to start from the bottom of the tree and return the height of the subtree rooted at a given node to its parent. The height of a subtree rooted at any node is one more than the maximum height of the left or right subtree.

The algorithm can be implemented as follows in C++, Java, and Python. Here, we pass diameter by reference to the function (instead of returning it) and update its value within the function itself using the left and right subtree height.

C++


Download  Run Code

Output:

The diameter of the tree is 6

Java


Download  Run Code

Output:

The diameter of the tree is 6

Python


Download  Run Code

Output:

The diameter of the tree is 6

The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The program requires O(h) extra space for the call stack, where h is the height of the tree.