{"id":14891,"date":"2023-03-24T06:03:55","date_gmt":"2023-03-24T06:03:55","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=14891"},"modified":"2023-11-30T07:18:25","modified_gmt":"2023-11-30T07:18:25","slug":"diameter-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/diameter-of-a-binary-tree\/","title":{"rendered":"Diameter of a Binary Tree"},"content":{"rendered":"

\"\"<\/p>\n

The diameter of a binary tree is a fundamental metric used in understanding the structure and efficiency of tree-based algorithms. It represents the longest path between any two nodes in the tree, measured by the number of edges between them. Calculating the diameter of a binary tree involves traversing the tree and finding the maximum distance between two nodes. This critical measurement plays a significant role in optimizing algorithms, such as tree-based data structures, network routing, and more.<\/p>\n

How to Find the Diameter of a Binary Tree?<\/h2>\n

Given a binary tree, find its diameter. The diameter of a binary tree refers to the longest distance between any two nodes in the binary tree and there is no compulsion on the path, it may or may not pass through the root node.
\nLet\u2019s understand this with the help of some sample examples.<\/p>\n

Example 1<\/strong><\/p>\n

Input<\/strong><\/p>\n

\"\"<\/p>\n

Output<\/strong><\/p>\n

4<\/code><\/pre>\n
Explanation of the above example<\/strong>
\nIn the above example, the longest path is of length 4 and the path is 7 – 4 – 8 – 1 – 3.<\/p>\n
Example 2<\/strong><\/p>\n
Input<\/strong><\/p>\n
\"\"<\/p>\n
Output<\/strong><\/p>\n
6<\/code><\/pre>\n
Explanation of the above example<\/strong>
\nIn the above example, the longest path is of length 6 and is not passing through the root. And the path is 5 – 3 – 1 – 8 – 0 – 2 – 0.<\/p>\n
Solution for Finding the Diameter of Binary Tree: Brute Force<\/h2>\n
In this approach, we will consider every node of the binary tree as the curving point. We can understand a curving point as the diameter path which has the maximum height. In the above-mentioned example, the curving points are 4 and 8 respectively.
\nThe diameter is nothing but the maximum of the height of the left subtree+ height of the right subtree. So in this approach, we will travel to each node and calculate the height of its left and right subtree and find the maximum. After traversing the complete binary tree we will have our diameter with us.<\/p>\n
Algorithm of Finding the Diameter of Binary Tree by Brute Force<\/h3>\n
We have explained the algorithm of the above-mentioned approach below.<\/p>\n
    \n
  • Travel the whole tree recursively.<\/li>\n
  • At each node calculate the height of the left and right subtree.<\/li>\n
  • Now calculate the diameter by adding the length of both the left and right subtrees.<\/li>\n
  • Now calculate the maximum diameter.<\/li>\n
  • You can do this by passing any variable by reference and with each recursive call updating the value of that variable.<\/li>\n<\/ul>\n
    Dry Run of the above Approach<\/h3>\n
    Now, we will discuss the dry run for the brute force of finding the diameter of a binary tree.<\/p>\n
    \"\"<\/p>\n
      \n
    • First, we will initialize the maximum diameter variable with the minimum value possible so INT_MIN.<\/li>\n
    • Now on node 5, the left height is 1, right height is 4 hence the value of diameter is 1+4=5. Currently, it is the max value so currently, so the diameter is 5.<\/li>\n
    • On node 9 the left height and right height are 0 as it is a leaf node so its diameter is 0 but it is not the maximum value we have so the diameter is currently 5.<\/li>\n
    • On node 4 the left height and right height are 3 hence the diameter is 6 so is the max value now.<\/li>\n
    • On node 7 left height is 2 right height is 0 current diameter is 2 but not max.<\/li>\n
    • For node 2 the left height is 1 and the right height is 1 so the diameter is 1 but not the max value.<\/li>\n
    • 12 is a leaf node so the diameter for leaf nodes like 12,0,3 in the above example will be 0.<\/li>\n
    • Similarly, we can do this for the remaining nodes, as we have explained in the image. But they will not change the value of the max diameter as they are smaller than the current max value.<\/li>\n<\/ul>\n
      Hence the maximum value of diameter will be 6.<\/p>\n\t\t\t\t\t\t