Difficulty: Easy · LeetCode 543

Problem

Given the root of a binary tree, return the length of the diameter of the tree (longest path between any two nodes).

Understanding the problem

The longest path passing through node u is left_height + right_height. The overall diameter is the max of this value across all nodes.

Intuition

Calculate height and diameter in the same bottom-up DFS traversal.

Approach

Initialize diameter = 0.
Define dfs(node): if node is None return 0.
Get left = dfs(node.left) and right = dfs(node.right).
Update diameter = max(diameter, left + right).
Return node height: 1 + max(left, right).

Naive Solution

For every node, separately calculate the height of its left and right subtree.

Python

class Solution:
    def diameterOfBinaryTree(self, root):

        def height(node):
            if not node:
                return 0

            return 1 + max(
                height(node.left),
                height(node.right)
            )

        if not root:
            return 0

        left_diameter = self.diameterOfBinaryTree(root.left)
        right_diameter = self.diameterOfBinaryTree(root.right)

        current = height(root.left) + height(root.right)

        return max(current, left_diameter, right_diameter)

C++

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;

        int leftDiameter = diameterOfBinaryTree(root->left);
        int rightDiameter = diameterOfBinaryTree(root->right);

        int current = height(root->left) + height(root->right);

        return max({current, leftDiameter, rightDiameter});
    }

private:
    int height(TreeNode* node) {
        if (!node) return 0;
        return 1 + max(height(node->left), height(node->right));
    }
};

Java

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        int leftDiameter = diameterOfBinaryTree(root.left);
        int rightDiameter = diameterOfBinaryTree(root.right);

        int current = height(root.left) + height(root.right);

        return Math.max(current, Math.max(leftDiameter, rightDiameter));
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

JavaScript

var diameterOfBinaryTree = function(root) {
    const height = (node) => {
        if (!node) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    };

    if (!root) return 0;

    const leftDiameter = diameterOfBinaryTree(root.left);
    const rightDiameter = diameterOfBinaryTree(root.right);

    const current = height(root.left) + height(root.right);

    return Math.max(current, leftDiameter, rightDiameter);
};

Time: O(n^2) worst case · Aux Space: O(h)

Optimized Code (Python 3)

Python

class Solution:
    def diameterOfBinaryTree(self, root):
        diameter = 0

        def dfs(node):
            nonlocal diameter

            if not node:
                return 0

            left = dfs(node.left)
            right = dfs(node.right)

            diameter = max(diameter, left + right)

            return 1 + max(left, right)

        dfs(root)
        return diameter

C++

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        dfs(root, diameter);
        return diameter;
    }

private:
    int dfs(TreeNode* node, int& diameter) {
        if (!node) return 0;

        int left = dfs(node->left, diameter);
        int right = dfs(node->right, diameter);

        diameter = max(diameter, left + right);

        return 1 + max(left, right);
    }
};

Java

class Solution {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        dfs(root);
        return diameter;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int left = dfs(node.left);
        int right = dfs(node.right);

        diameter = Math.max(diameter, left + right);

        return 1 + Math.max(left, right);
    }
}

JavaScript

var diameterOfBinaryTree = function(root) {
    let diameter = 0;

    const dfs = (node) => {
        if (!node) return 0;

        const left = dfs(node.left);
        const right = dfs(node.right);

        diameter = Math.max(diameter, left + right);

        return 1 + Math.max(left, right);
    };

    dfs(root);
    return diameter;
};

Time: O(n) · Aux Space: O(h)

Takeaway

Pattern: Postorder DFS + return useful information upward. This pattern is extremely important.