Diameter Of Binary Tree - Leetcode Solution

Problem:

Given the root of a binary tree, return 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.

Solution:

The diameter of a binary tree is defined as the maximum of the following three values:

The diameter of the left subtree from the root node. The diameter of the right subtree from the root node. The longest path between any two nodes that goes through the root node.

Therefore, the solution involves recursively computing the height of left and right subtrees of every node and taking the maximum of the sum of their heights plus 1.

Firstly, we check for an empty tree, if the root is None return 0.

Secondly, recursively calculate the max depth of left and right child of the root node.

Then, compute the maximum diameter of all maximum depths. Here, the maximum diameter is the maximum of the following three values:

• The diameter of the left subtree from the root node.
• The diameter of the right subtree from the root node.
• The longest path between any two nodes that goes through the root node (which is the sum of the maximum depths of left and right subtree plus 1).

Code:

Here is the python implementation for the solution of Diameter of Binary Tree problem:

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # Base case
        if not root:
            return 0
        
        # Compute the maximum depth of left and right subtree recursively
        l_depth = self.maxDepth(root.left)
        r_depth = self.maxDepth(root.right)
        
        # Compute the maximum diameter of all maximum depths
        max_diameter = max(l_depth + r_depth, 
                           self.diameterOfBinaryTree(root.left), 
                           self.diameterOfBinaryTree(root.right))
        return max_diameter
    
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        # Base case
        if not root:
            return 0
        
        # Compute the maximum depth of left and right subtree recursively
        l_depth = self.maxDepth(root.left)
        r_depth = self.maxDepth(root.right)
        
        # Return the one with greater sum plus 1
        return max(l_depth, r_depth) + 1

The time complexity of the above solution is O(n^2), where n is the number of nodes in the binary tree. This is because we are computing the maximum depth of left and right subtrees of every node, which takes O(n) time.

However, we can optimize the solution by computing the maximum depth and diameter of the binary tree in a single traversal. This can be done by keeping track of the maximum diameter of all nodes while computing the maximum depth. The optimized solution has a time complexity of O(n).

1