Algorithm Notes
Summary: Diameter Of Binary Tree — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.
Big-O Guide
Source
"""
Diameter Of Binary Tree
Problem: Diameter of Binary Tree
LeetCode link: https://leetcode.com/problems/diameter-of-binary-tree/
Description: Find the length of the longest path between any two nodes in a binary tree. The path may or may not pass through the root.
"""
from src.interview_workbook.leetcode._registry import register_problem
from src.interview_workbook.leetcode._types import Category, Difficulty
class Solution:
def solve(self, root) -> int:
"""
Find the diameter of a binary tree.
The diameter is defined as the length of the longest path between any two nodes.
"""
self.diameter = 0
def depth(node):
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
self.diameter = max(self.diameter, left + right)
return max(left, right) + 1
depth(root)
return self.diameter
def demo():
"""Run a simple demonstration of diameter of binary tree."""
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a test tree:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)
sol = Solution()
result = sol.solve(root)
print("Running demo for Diameter of Binary Tree...")
print(f"Diameter of binary tree: {result}")
return f"Diameter of binary tree: {result}"
register_problem(
id=543,
slug="diameter_of_binary_tree",
title="Diameter of Binary Tree",
category=Category.TREES,
difficulty=Difficulty.EASY,
tags=["tree", "binary_tree", "dfs"],
url="https://leetcode.com/problems/diameter-of-binary-tree/",
notes="",
)