Simple tree with root and two children
Input
diameter_of_binary_tree(TreeNode(1, TreeNode(2), TreeNode(3)))
Output
3
Longest path is 2 -> 1 -> 3, which includes 3 nodes.
Full lesson preview
Compute the diameter of a binary tree
Compute the diameter (longest path) of a binary tree measured in nodes.
Python practice25 minTrees & Binary TreesAdvancedLast updated March 29, 2026
Problem statement
Given the root of a binary tree, return the diameter of the tree. The diameter is defined as the number of nodes on the longest path between any two nodes in the tree. The path may or may not pass through the root. For an empty tree, the diameter is 0.
You should implement a function diameter_of_binary_tree(root) that returns an integer representing the diameter (in nodes). Aim for O(n) time using a single post-order traversal that computes heights and updates the maximum diameter.
Task
Implement an efficient algorithm to compute the diameter (number of nodes on the longest path between any two nodes) of a binary tree using DFS and recursion.
Examples
Input format
A single binary tree root (TreeNode or None). The TreeNode constructor is TreeNode(val, left=None, right=None).
Output format
An integer representing the diameter measured in nodes.
Constraints
The number of nodes in the tree is in the range [0, 10^5]. Node values can be any integers but are not relevant to the diameter calculation. Aim for O(n) time and O(h) recursion space where h is the tree height.
Samples
Sample 1
Input
diameter_of_binary_tree(TreeNode(1))
Output
1
Single-node tree has diameter 1 (the node itself).