543. Diameter of Binary Tree

Description

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

Intuition

The diameter of a binary tree can be determined by finding the longest path that goes through each node and keeping track of the maximum of these paths. For each node, this longest path can be calculated by the sum of the heights of its left and right subtrees.

Approach

1. Initialize a variable maxDiameter to keep track of the maximum diameter encountered.
2. Define a recursive function dfs that returns the height of a node.
3. In the dfs function: - If the node is null, return 0. - Recursively call dfs for the left and right children to get their heights. - Update maxDiameter with the maximum value of the sum of the left and right heights. - Return the maximum height of the left or right subtree plus one (to account for the current node).
4. Call the dfs function with the root node.
5. Return the value of maxDiameter.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the tree. Each node is visited once.

Space Complexity:

O(h), where h is the height of the tree. This space is used by the recursion stack.

Code

C++

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int maxDiameter = 0;
        
        std::function dfs = [&](TreeNode* node) {
            if (!node) return 0;
            
            int left = dfs(node->left);
            int right = dfs(node->right);
            
            maxDiameter = std::max(maxDiameter, left + right);
            
            return std::max(left, right) + 1;
        };
        
        dfs(root);
        return maxDiameter;
    }
};

Python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_diameter = 0

        def dfs(node):
            if not node:
                return 0
            left_height = dfs(node.left)
            right_height = dfs(node.right)
            # Update the diameter if the path through the current node is larger
            self.max_diameter = max(self.max_diameter, left_height + right_height)
            # Return the height of the tree
            return max(left_height, right_height) + 1

        dfs(root)
        return self.max_diameter

Java

class Solution {
    private int maxDiameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return maxDiameter;
    }
    
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        
        int left = dfs(node.left);
        int right = dfs(node.right);
        
        maxDiameter = Math.max(maxDiameter, left + right);
        
        return Math.max(left, right) + 1;
    }
}

JavaScript

var diameterOfBinaryTree = function(root) {
    let max = 0
    function dfs(node) {
        if (!node) return 0
        const left = dfs(node.left)
        const right = dfs(node.right)
        console.log(node.val, left, right)

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

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