Diameter of Binary Tree

543.Diameter of Binary Tree

Tree

DFS

Recursion

Problem Statement:

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.

Example:

Input:

root = [1,2,3,4,5]

→

Output:

3

Java Solution:

// Basic problem, its just calculating depth remember just to count L + R + 1
// You have to subtract 1 because they are only counting the path length (# edges)
class Solution {
    int ans;
    
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;  // Subtract 1 to get edge count
    }
    
    public int depth(TreeNode node) {
        if (node == null) return 0;
        
        int L = depth(node.left);   // Left subtree depth
        int R = depth(node.right);  // Right subtree depth
        
        ans = Math.max(ans, L + R + 1);  // Update max path including current node
        
        return Math.max(L, R) + 1;  // Return max depth through this node
    }
}

Python Solution:

def diameterOfBinaryTree(self, root: TreeNode) -> int:
    self.ans = 1
    
    def depth(node: TreeNode) -> int:
        if not node: return 0
        
        left = depth(node.left)   # Left depth
        right = depth(node.right) # Right depth
        
        self.ans = max(self.ans, left + right + 1)  # Update max path
        
        return max(left, right) + 1  # Return max depth
    
    depth(root)
    return self.ans - 1

C++ Solution:

class Solution {
private:
    int ans;
    
    int depth(TreeNode* node) {
        if(!node) return 0;
        
        int left = depth(node->left);   // Left depth
        int right = depth(node->right); // Right depth
        
        ans = max(ans, left + right + 1);  // Update max path
        
        return max(left, right) + 1;  // Return max depth
    }
    
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 1;
        depth(root);
        return ans - 1;  // Subtract 1 for edge count
    }
};

Complexity:

Time: O(N) where N is number of nodes
Space: O(H) where H is height of tree