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

Explanation

We can use depth-first search to traverse the tree and calculate the diameter. The diameter of a tree is equal to the maximum depth of the left subtree plus the maximum depth of the right subtree. Because the diameter is the sum of the maximum depths of the left and right subtrees, our DFS function must return the maximum depth of the subtree rooted at the current node.

Thus we only need to keep track of the maximum diameter found so far and update it whenever we find a larger diameter.

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

Complexity

\(n\) is the number of nodes in the tree, and \(d\) is the maximum depth of the tree

Measure	Complexity	Notes
Time	\(O(n)\)	visit each node once
Auxiliary Space	\(O(d)\)	recursive call stack

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.