text: Q:
  
  # Diameter of Binary Tree
  
  Given a Binary Tree, find diameter of it. The diameter of a tree is the number of nodes on the longest path between two leaves in the tree.
  
  Example:
  
  ```    For the above tree:
  
  Diameter is 7
  
  Longest paths:
  11->6->7->2->5->.9->4
  5->6->7->2->5->9->4
  
  Both have 7 nodes```
  
  Diameter of a tree
  
  Diameter of a tree is number of nodes on the longest path between two leaves of tree.
  
  Now the fact is the longest path always passes through the root.
  
  In fact no of nodes=height of left subtree (there is the source/destination leaf node) + height of right subtree(there is the destination/source leaf node) + 1(for root)
  
  So actually the solution depends on finding the height of each subtree.
  
  Finding height of each subtree can be done using recursion or level order traversal. However, I prefer level order traversal (BFS rocks!)
  
  Algorithm:
  
  Diameter=height of left subtree + height of right subtree+1
  
  Pre-requisite:
  
  A Queue q for level-order traversal, input binary tree, function to calculate height of subtrees
  
  ```FUNCTION height (root)
  1.  Set h=1;
  EnQueue (q, root);
  EnQueue (q, NULL);
  While(q is not empty)
  temp=DeQueue(q)
  IF(temp is NULL)
  IF(q is not empty)
  EnQueue (q, NULL);
  h++; //increment height as this is the end of the processed level
  End IF
  ELSE
  IF(temp->left)
  EnQueue (temp->left);
  IF(temp->right)
  EnQueue (temp->right);
  End IF-ELSE
  End While
  
  2.  Return h; //height of the tree
  End FUNCTION
  ```
  ```FUNCTION diameter (root)
  Return height (root->left) +height(root->right) +1;
  End FUNCTION```
  
  C++ implementation
  
  ``````#include <bits/stdc++.h>
  using namespace std;
  
  // tree node is defined
  class TreeNode{
  public:
  int data;
  TreeNode *left;
  TreeNode *right;
  };
  
  // creating new node for tree
  TreeNode* newnode(int data)
  {
  TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  
  return(node);
  }
  
  int height(TreeNode* node){
  int h=1;
  queue<TreeNode*> q;
  Node* temp;
  
  q.push(node);
  q.push(NULL);
  while(!q.empty()){
  temp=q.front();
  q.pop();
  if(!temp){
  if(!q.empty()){
  q.push(NULL);
  h++;
  }
  }
  else{
  if(temp->left)
  q.push(temp->left);
  if(temp->right)
  q.push(temp->right);
  }
  }
  return h;
  }
  
  int diameter(TreeNode* node)
  {
  if(node==NULL)
  return 0;
  return height(node->left)+height(node->right)+1;
  }
  
  int main() {
  //**same tree is builted as shown in example**
  int k;
  cout<<"same tree is built as shown in example\n";
  
  TreeNode *root=newnode(2);
  
  root->left= newnode(7);
  root->right= newnode(5);
  root->right->right=newnode(9);
  root->right->right->left=newnode(4);
  root->left->left=newnode(2);
  root->left->right=newnode(6);
  root->left->right->left=newnode(5);
  root->left->right->right=newnode(11);
  
  cout<<"Diameter of the tree is:\n"<<diameter(root);
  
  return 0;
  }
  ``````
  
  Output
  
  ```same tree is built as shown in example
  Diameter of the tree is:
  7 ```
  
  Example with explanation:
  
  ```For our example tree
  Calculating height of left-subtree
  
  Root=2;
  Root->left=7
  Root->right=5
  ------------------------------------------
  
  height(7)
  h=1
  root=7
  Push 7
  Push NULL
  Queue status:
  7, NULL
  
  1st iteration
  Queue not empty
  Queue front is 7
  Pop 7
  Push: 7->left(2) & 7->right(6)
  Queue status: NULL, 2, 6
  ------------------------------------------
  
  2nd iteration
  Queue not empty
  Queue front is NULL
  Pop NULL
  Increment h; h=2
  Push: NULL
  Queue status: 2, 6, NULL
  ------------------------------------------
  
  3rd iteration
  Queue not empty
  Queue front is 2
  Pop 2
  Push: Nothing ( 2->left (NULL) and 7->right (NULL)
  Queue status:  6, NULL
  ------------------------------------------
  
  4th iteration
  Queue not empty
  Queue front is 6
  Pop 6
  Push: 6->left (5) 6->right (11)
  Queue status: NULL, 5,11
  ------------------------------------------
  
  5th iteration
  Queue not empty
  Queue front is NULL
  Pop NULL
  Increment h//h=3
  
  Push: NULL
  Queue status: 5, 11, NULL
  ------------------------------------------
  
  6th iteration
  Queue not empty
  Queue front is 5
  Pop 5
  Push: Nothing (5->left is NULL, 5->right is NULL)
  Queue status: 11, NULL
  ------------------------------------------
  
  7th iteration
  Queue not empty
  Queue front is 11
  Pop 11
  Push: Nothing (11->left is NULL, 11->right is NULL)
  Queue status: NULL
  ------------------------------------------
  
  8th iteration
  Queue not empty
  Queue front is NULL
  Pop NULL
  Queue is empty
  So no more pushing NULL
  ------------------------------------------
  
  Queue is empty, hence end
  Thus height of left subtree is 3
  
  Same way we can proceed to calculate right subtree height which is also 3
  Thus diameter of the tree is 3+3+1=7```
metadata: {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}