Diameter of Binary Tree

EasyTree DFSNeetCode 150JuniorOpen on LeetCodeUpdated Sep 21, 2026

You're given the root of a binary tree. Return its diameter: the length of the longest path between any two nodes, counted as the number of edges on the path (not the number of nodes). The path may or may not pass through the root, and it never visits a node twice. A tree with a single node has diameter 0.

Examples

root = [1,2,3,4,5] returns 3

4, 2, 1, 3 is a longest path: 3 edges.

The path 4 -> 2 -> 1 -> 3 uses 3 edges, and so does 5 -> 2 -> 1 -> 3. No path in this tree is longer.

root = [1,2] returns 1

The only path joins 1 and 2, and it has a single edge.

root = [1,2,null,3,4,5,null,null,6] returns 4

The longest path skips the root entirely.

The path 5 -> 3 -> 2 -> 4 -> 6 has 4 edges and never touches the root. Any path through the root 1 has at most 3 edges.

Constraints

1 <= number of nodes <= 10^4
-100 <= Node.val <= 100

Hints

Hint 1

Every path has one highest node where it turns. How long can a path that turns at a given node be?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Post-order depth-first search (DFS) that returns each subtree's height while tracking a global best. The longest path whose highest node is X runs down X's left side and down its right side, so its length in edges is height(left) + height(right). Check that at every node during one pass and keep the max, returning 1 + max(left, right) to the parent. O(n) time, O(h) space for recursion, h = tree height.

Time

O(n)

Space

O(h)

Pitfall

Computing height(left) + height(right) only at the root misses diameters that live entirely inside one subtree, like the third example. Also keep units straight: the answer counts edges, not nodes.

Solutions

class Solution {
    private int best;

    public int diameterOfBinaryTree(TreeNode root) {
        best = 0;
        height(root);
        return best;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;
        int left = height(node.left);
        int right = height(node.right);
        best = Math.max(best, left + right);
        return 1 + Math.max(left, right);
    }
}

from typing import Optional

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0

        def height(node: Optional[TreeNode]) -> int:
            nonlocal best
            if not node:
                return 0
            left = height(node.left)
            right = height(node.right)
            best = max(best, left + right)
            return 1 + max(left, right)

        height(root)
        return best