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


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 = TreeNode(vals[0])
        queue = [root]
        i = 1
        while i < len(vals):
            node = queue.pop(0)
            if i < len(vals) and vals[i] is not None:
                node.left = TreeNode(vals[i])
                queue.append(node.left)
            i += 1
            if i < len(vals) and vals[i] is not None:
                node.right = TreeNode(vals[i])
                queue.append(node.right)
            i += 1
        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.