Diameter of Binary Tree

Problem

The diameter of a binary tree is defined as the length of the longest path between any two nodes within the tree. The path does not necessarily have to pass through the root.

The length of a path between two nodes in a binary tree is the number of edges between the nodes. Note that the path can not include the same node twice.

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

Examples

Example 1:

Input: root = [1,null,2,3,4,5]

Output: 3

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

Example 2:

Input: root = [1,2,3]

Output: 2

Constraints

• 1 <= number of nodes in the tree <= 100
• -100 <= Node.val <= 100

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Solution

Invariant of the DFS is the longest path through the node. We check left and right side, update maximum using diameter through left and right, and then pass up the longer of the two as we are going up through the current node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
 
        // Invariant: max diameter coming from this node
        std::function<int(TreeNode*)> dfs;
        dfs = [&](TreeNode *node) -> int {
            if (!node) { return 0; }
            int dia_left = dfs(node->left);
            int dia_right = dfs(node->right);
            diameter = std::max(diameter, dia_left + dia_right);
            return 1 + std::max(dia_left, dia_right);
        };
        dfs(root);
        return diameter;
    }
};