Problem Statement

Description

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.

The length of a path between two nodes is represented by the number of edges between them.

Examples

Example 1:

flowchart TD a((1))-->b((2)) b-->c((4)) b-->d((5)) a-->e((3))
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints

  • The number of nodes in the tree is in the range [1, 104].
  • -100 <= Node.val <= 100

Key Insights

In this problem we are asked to find the length of the longest path between two nodes in a binary tree. Since we can only traverse a binary tree from top to bottom, we know that the answer to this problem will include some sort of tree traversal.

If we draw out an example tree, we can see that the longest possible path in a binary tree will start at one leaf node, pass through a lowest common ancestor, and then terminate at another leaf node. In the diagram below, we can see that the longest path in the binary tree passes through node 2. If we know the max height of the left and right subtrees, we can calculate the maximum path length.

Since we need to know the max height of the left and right subtrees for each node we visit, we will need to use a post-order traversal to solve this problem. We can base our solution on Leetcode 104: Maximum Depth of Binary Tree. Only in our case, we will add some logic to compare the longest path at each node to the global max path.

flowchart TD a((1)) b((2)) c((3)) d((4)) e((5)) f((6)) g((7)) h((8)) i((9)) j((11)) k((12)) l((13)) m((14)) a-->b b-->c b-->d c-->g c-->h a-->f d-->i d-->e g-->j g-->k i-->l i-->m

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        """
            T: O(N)
            S: O(N) ~ worst; O(log N) ~ perfectly balanced

            This solution is based on:
            https://jessechaulk.com/posts/104-maximum-depth-of-binary-tree/
        """
        self.ans = 0

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

            # Find the max height of the left and right subtrees
            left = helper(node.left)
            right = helper(node.right)

            # Check the sum of the left + right subtrees and update the
            # longest path variable if applicable.
            self.ans = max(self.ans, left + right)

            # Return the height of the max of the left and right subtrees.
            # Add 1 to the result to account for the height of the current 
            # node
            return max(left, right) + 1

        helper(root)

        return self.ans