DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Diameter of Binary Tree

easyTrees

Problem statement

Given the root of a binary tree, return the length of its diameter: the longest path between any two nodes, measured in edges. The path can go up and then down through any node, and it does not have to pass through the root.

An empty tree or a single node has diameter 0. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [10, 4, 12, 2, 6]

Output: 3

Explanation: 2 -> 4 -> 10 -> 12 has three edges.

Example 2

Input: root = [8, 3, null, 1, 5, 0, null, null, 6]

Output: 4

Explanation: 0 -> 1 -> 3 -> 5 -> 6 is the longest path, and it never touches the root 8.

Hints

Approach

Compute every height once, bottom-up, and check the diameter at each node while you have both child heights in hand.

  1. height(node) returns 0 for an empty node.
  2. Otherwise it computes left = height(node.left) and right = height(node.right).
  3. Before returning, it updates best = max(best, left + right). That sum is the number of edges on the longest path peaking here.
  4. It returns 1 + max(left, right) to its parent.

The function returns one thing (the height) and records another (the diameter) on the side. This "return one value, track another" post-order pattern solves many tree problems, such as maximum path sum.

ComplexityTime O(n)Space O(h)
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional["TreeNode"]) -> int:
best = 0
def height(node) -> int:
nonlocal best
if node is None:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right) # longest path peaking here, in edges
return 1 + max(left, right)
height(root)
return best

Follow-up questions

  • Return the two end nodes of the diameter, not just its length.
  • Each node now has a value; return the maximum sum of values along any path.

Frequently asked questions

The heights count nodes below the peak on each side. A path with left nodes on one side and right on the other has exactly one edge per one of those nodes, connecting it towards the peak, so the edge count is left + right.

The longest path may lie entirely inside one subtree, as in the second example where the root has only one child. You must consider every node as the peak.

The same idea measures the worst-case hop count between any two nodes in a tree-shaped network, such as a hierarchy of switches or a replication tree. It also checks that you can combine results from children in a single pass instead of recomputing them.