Diameter of a Binary Tree

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. (1 + height if left subtree + height of right subtree)
2. Diameter of the left subtree
3. 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.