Diameter of Binary Tree

Problem

https://leetcode.com/problems/diameter-of-binary-tree/

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.

Example 1:

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, 10:sup:`4`].

• -100 <= Node.val <= 100

Pattern

Tree, Depth-First Search, Binary Tree

Approaches

DFS

Code

from __future__ import annotations

from collections import deque


class TreeNode:
    """Node in a binary tree."""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    @classmethod
    def from_list(cls, vals: list[int | None]) -> TreeNode | None:
        if not vals:
            return None

        root = cls(vals[0])
        queue = deque([root])
        children = iter(vals[1:])

        while queue:
            node = queue.popleft()
            for side in ("left", "right"):
                val = next(children, None)
                if val is not None:
                    child = cls(val)
                    setattr(node, side, child)
                    queue.append(child)

        return root


def diameterOfBinaryTree(root: TreeNode | None) -> int:
    """Return the diameter of the binary tree."""
    result = 0

    def dfs(node: TreeNode | None) -> int:
        nonlocal result
        if node is None:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        result = max(result, left + right)
        return 1 + max(left, right)

    dfs(root)
    return result

Test

>>> from diameter_of_binary_tree__dfs import TreeNode, diameterOfBinaryTree
>>> diameterOfBinaryTree(TreeNode.from_list([1, 2, 3, 4, 5]))
3
>>> diameterOfBinaryTree(TreeNode.from_list([1, 2]))
1

class diameter_of_binary_tree__dfs.TreeNode(val=0, left=None, right=None)

Bases: object

Node in a binary tree.

classmethod from_list(vals: list[int | None]) → TreeNode | None

diameter_of_binary_tree__dfs.diameterOfBinaryTree(root: TreeNode | None) → int

Return the diameter of the binary tree.