In this chapter we shall solve how to find out diameter of a binary tree.
Problem statement:
You are given root node of a binary tree, you need to find the diameter in that tree.
Now wait a minute,
Diameter term is usually used in reference to a circle, but how is it possible to use it with tree?
In tree diameter is usually referred to longest path between 2 leaf nodes in the tree.
Consider the given example:
Here the diameter is the longest path between 2 leaf nodes is:
h -> e -> b -> a -> c -> f -> i -> j
The path is shown in below image
In this tutorial we shall see how to solve.
So from the image above, we ca see that the diameter is equal to [ height of left sub tree + height of right sub tree + 1].
The above formula works if the diameter is passing through the root. What if the diameter is not passing through root as shown in the example below:
In the above image, the diameter will not pass through the root, but rather it will pass through the root of another sub tree.
Hence in this situation, we use the below formula.
Max(left_diameter, right_diameter)
So our full formula will be:
Max(left_height + right_height + 1, max(left_diameter, right_diameter)).
So our function will be as below:
int diameter (node *p)
{
if (p == NULL)
return 0;
int left_height = height(p -> left)
int right_height = height(p -> right)
int left_diameter = diameter(p -> left)
int right_diameter = diameter(p -> right)
int result = max (left_height+ right_height + 1, max (left_diameter, right_diameter))
}
From the function above,
left_height will calculate the left height
right_height will calculate the right height
left_diameter is used to calculate the left sub tree diameter
right_diameter is used to calculate the right sub tree diameter
Finally, we will arrive at the result.
Solution in C++
#include <iostream> #include <stack> #include <map> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int height(Node* node) { if(node == NULL) return 0; return 1 + max(height(node->left), height(node->right)); } int max(int a, int b) { return (a > b)? a : b; } int get_diameter_of_b_tree(Node * tree) { if (tree == NULL) return 0; int lheight = height(tree->left); int rheight = height(tree->right); int l_diameter = get_diameter_of_b_tree(tree->left); int r_diameter = get_diameter_of_b_tree(tree->right); return max(lheight + rheight + 1, max(l_diameter, r_diameter)); } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); int diameter = get_diameter_of_b_tree(root); cout<<"The diameter is = "<<diameter<<endl; return 0; }
Output:
The diameter is = 5