Skip to main content

543. Diameter of Binary Tree

easy

Find the length of the longest path between any two nodes in a binary tree, measured in edges. The path need not pass through the root — solve with single-pass DFS returning depth and updating a global max.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • -100 <= Node.val <= 100

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

For every node, the longest path THROUGH that node = depth(left) + depth(right).

Hint 2

Take the max of those over all nodes — that's the diameter.

Hint 3

Compute depth with the same DFS that's updating the diameter — one pass total.

Solution approach

Reveal approach

DFS returning depth, updating a global diameter. Helper depth(node): if null return 0; left = depth(node.left); right = depth(node.right); diameter = max(diameter, left + right); return 1 + max(left, right). The diameter variable is updated for every node visited, since each node is the apex of at most one optimal path. Return diameter at the end. O(n) time, O(h) recursion space.

Complexity

Time
O(n)
Space
O(h)

Related patterns

  • dfs
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

More Trees practice problems

See all Trees problems →