Finding the Diameter of a Binary Tree – LeetCode Solution [Easy]

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.

It can be computed by finding the longest path between two nodes in the tree.

LeetCode Problem Link

Example

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Approach

The diameter of a binary tree is the maximum of the following three quantities:

• Diameter of the left subtree.
• Diameter of the right subtree.
• Longest path between two nodes which passes through the root.

To solve this problem, we can use a recursive approach. We define a function computeHeight that calculates the height of each subtree while also updating the diameter as it traverses the tree. Then, we call this function from the main function diameterOfBinaryTree to get the diameter of the binary tree.

Time complexity: O(n), where n is the number of nodes in the binary tree. Since, we visit each node exactly once.

Pseudocode

function diameterOfBinaryTree(root):
    diameter = 0
    computeHeight(root, diameter)
    return diameter

function computeHeight(node, diameter):
    if node is null:
        return 0
    left_height = computeHeight(node.left, diameter)
    right_height = computeHeight(node.right, diameter)
    diameter = max(diameter, left_height + right_height)
    return max(left_height, right_height) + 1

Code Implementation

#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:

    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        computeHeight(root, diameter);
        return diameter;
    }
    
    int computeHeight(TreeNode* node, int& diameter) {
        if (!node) return 0;

        int left_height = computeHeight(node->left, diameter);
        int right_height = computeHeight(node->right, diameter);

        diameter = std::max(diameter, left_height + right_height);

        return max(left_height, right_height) + 1;
    }
};

Output

3