EasyTreeDepth-First SearchBinary TreeUpdated Sep 2026

543. Diameter of Binary Tree

Asked at Roblox

Difficulty

Easy

Time

O(n)

Space

O(h)

Pattern

Tree

Companies

1

Problem

You are given the root of a binary tree. Return the diameter of the tree.

The diameter is the number of edges on the longest path between any two nodes in the tree. The two nodes can be any two nodes — they do not have to be leaves, and the path does not have to pass through the root.

Note the unit: the answer counts edges, not nodes. A single node has diameter 0, and a parent with one child has diameter 1.

Longest path between any two nodes

4251bend point34 → 2 → 1 → 3, that is 3 edges
The path 4 → 2 → 1 → 3 has 3 edges, and no other pair of nodes is farther apart.

Constraints

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

Examples

Example 1
Inputroot = [1,2,3,4,5]
Output3
WhyThe longest path is 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3). It uses 3 edges, so the answer is 3. Notice it bends at the root here.
Example 2
Inputroot = [1,2]
Output1
WhyOnly two nodes exist, joined by one edge, so the longest path has length 1.

Asked At

1 companies
CompanyDifficulty
RobloxEasyView all Roblox questions →

How to Think About It

1

The longest path has some highest node, where it "bends". At that node, the path length is height(left) + height(right) (heights counted in edges from that node down).

2

Naive approach: for every node, compute both heights from scratch — O(n²) on a skewed tree.

3

Key insight: compute heights bottom-up in one post-order DFS. At each node, update a global best with lh + rh, then return 1 + max(lh, rh) to the parent.

4

Walkthrough for [1,2,3,4,5]: node 4 and 5 return 1; node 2 sees 1 + 1 = 2 and returns 2; node 3 returns 1; root sees 2 + 1 = 3. Answer 3 (path 4-2-1-3).

5

Define height of a null node as 0 and of a leaf as 1 — then lh + rh counts edges on the path through the current node.

Optimal Approach

Step 1: best = 0.
Step 2: depth(node):
If node is null, return 0.
lh = depth(node.left), rh = depth(node.right).
best = max(best, lh + rh).
Return 1 + max(lh, rh).
Step 3: Call depth(root) and return best.

Time: O(n). Space: O(h) for recursion.

One DFS, track the best bend

4leaf → 125leaf → 113Leaves 4 and 5 return height 142best = 1+1 = 2, return 2513leaf → 1Node 2 sees two children of height 1, so a path of 2 edges bendsthere4251best = 2+1 = 33The root sees heights 2 and 1, giving the final answer 3best = max(best, lh + rh)return 1 + max(lh, rh)
Each node reports its height upward, and before that it checks the path that bends at itself.
ComplexityTime O(n)Space O(h)Each node is visited once in a single post-order DFS; h is the tree height, which is the depth of the recursion stack.

What Trips People Up in Real Interviews

1

Returning height(root.left) + height(root.right). The longest path might sit entirely inside one subtree.

2

Counting nodes instead of edges. The problem asks for edges, so a single node has diameter 0.

3

Returning the diameter from the recursive function instead of the height. The function must return height to its parent and update the diameter on the side.

4

Recomputing heights for every node — say explicitly that the post-order pass makes it linear.

Solution Code

O(n) time
def diameterOfBinaryTree(root):
    best = 0

    def depth(node):
        nonlocal best
        if not node:
            return 0
        lh = depth(node.left)
        rh = depth(node.right)
        best = max(best, lh + rh)
        return 1 + max(lh, rh)

    depth(root)
    return best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Diameter of Binary Tree problem?

Diameter of Binary Tree asks for the number of edges on the longest path between any two nodes. The path does not have to pass through the root, which is exactly the detail the interviewer is checking.

How do you solve Diameter of Binary Tree?

The optimal approach runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Diameter of Binary Tree?

Diameter of Binary Tree is asked at Roblox. It is a easy difficulty problem.

What are common mistakes on Diameter of Binary Tree?
  • Returning `height(root.left) + height(root.right)`. The longest path might sit entirely inside one subtree.
  • Counting nodes instead of edges. The problem asks for edges, so a single node has diameter 0.
  • Returning the diameter from the recursive function instead of the height. The function must return height to its parent and update the diameter on the side.
  • Recomputing heights for every node — say explicitly that the post-order pass makes it linear.