Diameter of Binary Tree

Problem Description

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.

Examples

Constraints

• The number of nodes in the tree is in the range [1, 10⁴].
• -100 <= Node.val <= 100

Height Calculation and Path Aggregation

For any node, the longest path that passes through it as the highest point is the sum of the maximum heights of its left and right subtrees: diameter_at_node = left_height + right_height. We can compute this for all nodes in O(n) time using postorder DFS. We write a helper function that returns the height of a node:

1. If the node is null, return 0.
2. Recursively find the height of the left child (left_h) and right child (right_h).
3. Update our global maximum diameter: max_diameter = max(max_diameter, left_h + right_h).
4. Return the height of the current node to its parent: 1 + max(left_h, right_h).

Solution 1: DFS Height Accumulator

Traverse tree nodes via DFS, calculating height and updating the global maximum path.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    private int maxDiameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter = 0;
        calculateHeight(root);
        return maxDiameter;
    }

    private int calculateHeight(TreeNode node) {
        if (node == null) return 0;
        
        int leftHeight = calculateHeight(node.left);
        int rightHeight = calculateHeight(node.right);

        // Path passing through current node uses left + right child edges
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

        return 1 + Math.max(leftHeight, rightHeight); // return height to parent
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0
        
        def calculate_height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left_height = calculate_height(node.left)
            right_height = calculate_height(node.right)
            
            # Update diameter using current node as root path
            self.max_diameter = max(self.max_diameter, left_height + right_height)
            
            return 1 + max(left_height, right_height)

        calculate_height(root)
        return self.max_diameter

#include <algorithm>

/**
 * 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 {
private:
    int maxDiameter;

    int calculateHeight(TreeNode* node) {
        if (!node) return 0;
        int leftHeight = calculateHeight(node->left);
        int rightHeight = calculateHeight(node->right);

        maxDiameter = std::max(maxDiameter, leftHeight + rightHeight);

        return 1 + std::max(leftHeight, rightHeight);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDiameter = 0;
        calculateHeight(root);
        return maxDiameter;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we visit every node in the binary tree exactly once.
• Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

Where It Breaks

If the tree is extremely deep and unbalanced (e.g. skewed into a single linked list of size 10^5), the recursion stack can overflow.

Common Mistakes

• Incorrect leaf node height representation: Returning 1 instead of 0 when encountering a null node. This counts nodes rather than edges, introducing an off-by-one error.
• Forgetting to check non-root paths: Assuming the longest path must pass through the root node of the entire tree. The diameter path can reside entirely in a single branch of the subtree.

← All Problems