Skip to main content
DSA patterns

Diameter of Binary Tree

easyTrees Must-doMetaAmazonMicrosoft

Problem statement

You are given the root of a binary tree. Return its diameter: the length, in edges, of the longest path between any two nodes in the tree.

That path does not have to pass through the root, and it is not necessarily a straight top-to-bottom walk — it can go up one side of some node and back down the other. Think of it as the longest chain you could trace through a hierarchy, such as an org chart or a directory tree, where the chain is allowed to bend once at whichever node sits at its highest point.

Examples

Example 1

Input: root = [1,2,3,4,5]

Output: 3

Explanation: The longest path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3), which crosses 3 edges.

Example 1

Example 2

Input: root = [1,2]

Output: 1

Explanation: The tree has a single edge, between 1 and 2, so the diameter is 1.

Hints

Hint 1: For one specific node, the longest path that bends at that node is the height of its left subtree plus the height of its right subtree — try that on the root first.

Approach

Optimal: Height and diameter in one pass

Intuition

The brute-force approach recomputes each subtree's height every time an ancestor asks for it, which is why it is quadratic. The fix is to notice that a single height(node) function already visits every node in the tree once, in post-order (children finish before their parent). If, on the way back up from each node, you also compare height(left) + height(right) against the best answer so far, you get the diameter as a free side effect of the same pass, with no repeated work.

Steps

  1. Keep a running best value, starting at 0.
  2. Write height(node): an empty node returns 0.
  3. Otherwise, recursively get left = height(node.left) and right = height(node.right).
  4. Update best = max(best, left + right) — this is the longest path that bends at the current node.
  5. Return 1 + max(left, right) as this node's own height.
  6. Call height(root) once; the answer is the final value of best.

Dry run

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

node (post-order) left height right height best updated to returned height
4 0 0 0 1
5 0 0 0 1
2 1 (from 4) 1 (from 5) 2 2
3 0 0 2 1
1 2 (from 2) 1 (from 3) 3 3

Final best: 3, found without a single subtree being measured twice.

Edge cases: a single node returns height 1 with left and right both 0, so best stays 0 — correct, since there are no edges to cross.

Complexity

Time O(n) - Every node's height is computed exactly once, as part of a single post-order traversal, instead of once per ancestor that asks for it.

Space O(h) - Only the recursion's call stack is used, one frame per node on the current root-to-leaf path, so O(log n) for a balanced tree and up to O(n) for a skewed one.

class Solution:
    def diameterOfBinaryTree(self, root: "TreeNode | None") -> int:
        self.best = 0

        def height(node: "TreeNode | None") -> int:
            if node is None:
                return 0
            left = height(node.left)
            right = height(node.right)
            self.best = max(self.best, left + right)
            return 1 + max(left, right)

        height(root)
        return self.best


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values):
    from collections import deque

    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    n = len(values)
    while queue and i < n:
        node = queue.popleft()
        if i < n:
            v = values[i]
            i += 1
            if v is not None:
                node.left = TreeNode(v)
                queue.append(node.left)
        if i < n:
            v = values[i]
            i += 1
            if v is not None:
                node.right = TreeNode(v)
                queue.append(node.right)
    return root


if __name__ == "__main__":
    root1 = build_tree([1, 2, 3, 4, 5])
    root2 = build_tree([1, 2])
    sol = Solution()
    print(sol.diameterOfBinaryTree(root1))  # 3
    print(sol.diameterOfBinaryTree(root2))  # 1
RecapThe whole problem in a few lines, for the night before
  • Spot it: "longest path between any two nodes in a tree," measured in edges — the classic tree diameter question
  • Idea: at every node, the best path bending there is height(left) + height(right); get that height while checking every node exactly once
  • Cost: O(n) time, O(h) space for the recursion stack (up to O(n) for a skewed tree)
  • Trap: calling a separate height() function once per node re-walks subtrees and turns an O(n) pass into O(n²) — fold the diameter check into the same recursive height computation

Interview follow-ups

  • Return the actual longest path (the sequence of node values), not just its length.

    Track, alongside best, which node produced it and which of its two children fed the longer subtree, so the winning node becomes known once the pass finishes. Then walk down from that node twice — once repeatedly into whichever child has the larger height, until reaching a leaf, for each side — and concatenate the two walks (one reversed) with the winning node in the middle. This adds an O(h) reconstruction step after the O(n) pass, so the overall complexity is unchanged.

  • The tree is guaranteed to be balanced and can have millions of nodes. Does anything change?

    The time complexity stays O(n) either way, but the space bound improves in practice: a balanced tree keeps the recursion depth at O(log n), so the call stack never grows large. If the tree could still be adversarially skewed despite "usually" being balanced, converting the recursion into an iterative post-order traversal with an explicit stack removes the risk of exhausting the call stack on the rare skewed case, at the cost of a slightly more involved implementation.

Frequently asked questions

The problem defines diameter as a path length in edges, and a path with k edges always visits k + 1 nodes. Mixing the two up is the most common off-by-one mistake on this problem — a two-node tree has 1 edge (matching Example 2), not 2.

Because the deepest chain in the tree can live entirely inside one subtree, far from the top. A tree where the root has one short branch and one very deep, very lopsided branch has its longest path buried inside that deep branch, nowhere near the root — which is exactly why every node, not just the root, has to be checked.

Many infra structures are trees where the "longest chain" question matters directly: the deepest call chain in a service-dependency tree, the longest path in a build's task graph, or the longest chain of ownership references in a Kubernetes cluster. Diameter is the general version of "how deep can this hierarchy possibly get end to end," which is a real capacity or latency question.

Yes, the same idea works: at each node, take the two largest depths among all of its children (not just left and right) and add them, then recurse. The binary case in this problem is the same idea with "the two children" fixed as left and right instead of chosen from a longer list.

Yes — it is the node whose two subtree heights add up to the largest sum found during the pass, which is also the lowest common ancestor of the two endpoints of the longest path. Tracking which node produced the best sum, not just the sum itself, is exactly what the first follow-up below needs.