Skip to main content

Diameter of Binary Tree

Problem​

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    int ans;
    map<TreeNode*, int> mp;

   public:
    void traverse(TreeNode* root) {
        if (!root) return;
        traverse(root->left);
        traverse(root->right);
        int dist = 0;
        mp[root] = 0;
        if (root->left) {
            dist += mp[root->left] + 1;
            mp[root] = mp[root->left] + 1;
        }
        if (root->right) {
            dist += mp[root->right] + 1;
            mp[root] = max(mp[root], mp[root->right] + 1);
        }
        ans = max(ans, dist);
    }

    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        traverse(root);
        return ans;
    }
};