Diameter of Binary Tree (LeetCode 543)

Definition

• The diameter of a binary tree is the length of the longest path between any two nodes in the tree.
• This path may or may not pass through the root.
• The length of a path is the number of edges between nodes.

Example

• For a given tree, the diameter is the longest path and the number of edges in it.
  • Example: Path from one node to another via the root can give diameter = 4 edges.
  • If not using the root, another path might provide a longer diameter.

Key Points

• The diameter of the tree isn’t necessarily through the root.
• Every node can have a local diameter.
• The task is to find the maximum diameter among all nodes.

Steps to Solve

1. Depth-First Search (DFS) Approach: For each node, compute the diameter in terms of the height of its left and right subtrees.
2. Height Calculation:
   • Diameter of a node = Height of left subtree + Height of right subtree.
   • Update the global maximum diameter if the current node’s diameter is larger.
3. Height Function:
   • Base condition: If the node is null, its height is 0.
   • Recursive calculation: Height = 1 + max(Height of left subtree, Height of right subtree).
4. Updating Diameter:
   • Use a global variable to keep track of the largest diameter encountered.

Algorithm Outline

• Initialize largest_diameter = 0 (global variable).
• Define a helper function height(root) that calculates the height of a node and updates the diameter.
• For each node:
  • Calculate left_height and right_height.
  • Compute current_diameter = left_height + right_height.
  • Update largest_diameter = max(largest_diameter, current_diameter).
  • Return height: 1 + max(left_height, right_height).
• Call the height function on the root to trigger DFS and compute diameters.

Complexity

• Time Complexity: O(n), where n is the number of nodes. Each node is visited once.
• Space Complexity: O(H), where H is the height of the tree. This is for the call stack during DFS.

Code Implementation

class Solution:
    def diameterOfBinaryTree(self, root):
        largest_diameter = [0]

        def height(node):
            if not node:
                return 0
            left_height = height(node.left)
            right_height = height(node.right)
            current_diameter = left_height + right_height
            largest_diameter[0] = max(largest_diameter[0], current_diameter)
            return 1 + max(left_height, right_height)

        height(root)
        return largest_diameter[0]