Diameter of a Binary Tree

Problem Summary

• Given a root of a tree, return the diameter of the tree
• Diameter is the longest path between two nodes (doesn't have to pass through root)

Main Concepts Used

• Trees
• Tree Traversal
• Depth First Traversal
• Depth First Search

Time & Space Complexity

• Time: $O()$ → Reason:
• Space: $O(h)$ → Reason: Height of the tree in the recursive solution, which could be $O(n)$

Code

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

        def helper(root):
            nonlocal result
            if not root:
                return 0
            pathLeft = helper(root.left)
            pathRight = helper(root.right)
            result = max(result, pathLeft + pathRight)
            return 1 + max(pathLeft, pathRight)

        helper(root)
        return result

Common Mistakes / Things I Got Stuck On

• Not being able to figure out the main case
• Forgetting to use nonlocal again