The diameter or width of a tree is the count of nodes in the longest path from one leaf to another. Given a binary tree, you need to return the diameter of the tree.

In the tree above, the diameter is 7. The path using which the diameter is calculated is 4 -> 6 -> 3 -> 8 -> 10 -> 14 -> 13 . Note that the end points ( 4 and 13 in this case) should be leaf nodes.
Algorithm
The diameter of a tree is the maximum of the following quantities –
- (1 + height if left subtree + height of right subtree)
- Diameter of the left subtree
- Diameter of the right subtree
We can recursively calculate the diameter of the left and right subtrees with base case where the node is a null pointer. We can create a separate function to compute the height of the subtrees.
#include <bits/stdc++.h> using namespace std; struct Node{ Node* left; Node* right; int data; }; Node* createNode(int key){ Node* temp = new Node(); temp->data = key; temp->right = nullptr; temp->left = nullptr; return temp; } Node* root = nullptr; Node* insertNode(Node* node, int key){ Node* temp = createNode(key); if(root == nullptr){ root = temp; return root; } if(node == nullptr){ return temp; } if(key < node->data){ node->left = insertNode(node->left, key); }else if(key > node->data){ node->right = insertNode(node->right, key); } return node; } void levelOrderTraversal(){ Node* temp = root; queue<Node*> q; q.push(temp); while(!q.empty()){ Node* front = q.front(); cout<<front->data<<" "; q.pop(); if(front->left != nullptr){ q.push(front->left); } if(front->right != nullptr){ q.push(front->right); } } } int getHeight(Node* node){ if(node==nullptr){ return 0; } return 1 + max(getHeight(node->left), getHeight(node->right)); } int getDiameter(Node* node){ if(node == nullptr){ return 0; } int lheight = getHeight(node->left); int rheight = getHeight(node->right); int ldiameter = getDiameter(node->left); int rdiameter = getDiameter(node->right); return max(1+lheight+rheight, max(ldiameter, rdiameter)); } int main() { insertNode(root, 8); insertNode(root, 3); insertNode(root, 10); insertNode(root, 1); insertNode(root, 6); insertNode(root, 14); insertNode(root, 4); insertNode(root, 7); insertNode(root, 13); levelOrderTraversal(); cout<<endl; cout<<"Height of tree is: "<<getHeight(root)<<endl; cout<<"Diameter of the tree is: "<<getDiameter(root)<<endl; return 0; }
Also, check out another popular interview problem Arrival and Departure time in a graph.
One comment