543. Diameter of Binary Tree¶

Edited by Charles

Easy · Python · Binary Tree

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given the root of a binary tree, return the diameter of the tree.

The diameter is the length of the longest path between any two nodes in the tree.

Original study notes follow, including intermediate snippets and earlier attempts.

Problem¶

Given the root of a binary tree, return the diameter of the tree.

The diameter is the length of the longest path between any two nodes in the tree.

The path does not necessarily need to pass through the root.

The length of a path is measured by the number of edges, not the number of nodes.

Example¶

The longest path can be:

4 → 2 → 1 → 3

or:

5 → 2 → 1 → 3

There are 3 edges.

Therefore:

Output = 3

The key idea is to distinguish between two concepts:

The diameter passing through the current node
The maximum depth returned to the parent

This is very similar to LeetCode 124 — Binary Tree Maximum Path Sum.

For every node:

          node
         /    \
       left   right

we first recursively calculate:

leftDepth = self.traverse(node.left)
rightDepth = self.traverse(node.right)

Then we use these two depths to:

1. Update the global diameter
2. Return the maximum depth to the parent

Define:

traverse(node)

as:

The maximum depth starting from node and going downward along one branch.

For example:

Starting from 2, the longest downward path is:

2 → 4 → 6

Therefore:

traverse(2) = 3

Notice that this value represents the number of nodes in the downward path starting from 2.

This is why we return:

return 1 + max(leftDepth, rightDepth)

The 1 represents the current node.

If the current node does not exist:

if not node:
    return 0

An empty subtree has depth:

For a leaf node:

we get:

leftDepth = 0
rightDepth = 0

Therefore:

return 1 + max(0, 0)

which gives:

So a leaf node has depth 1.

We recursively calculate:

leftDepth = self.traverse(node.left)
rightDepth = self.traverse(node.right)

Because the current node needs information from both children before it can calculate its own result, this is a Postorder DFS:

Left
 ↓
Right
 ↓
Current Node

Suppose:

          node
         /    \
        A      B
       /        \
      ...       ...

The longest path passing through node can use:

deepest node in left subtree
        ↓
      ...
        ↓
       left
        ↓
       node
        ↓
      right
        ↓
       ...
        ↓
deepest node in right subtree

Therefore, the diameter passing through the current node is:

leftDepth + rightDepth

Why don't we add 1?

Because the diameter is measured by the number of edges.

For example:

At node 1:

leftDepth = 2
rightDepth = 1

The path is:

4 → 2 → 1 → 3

The number of edges is:

4 → 2    1 edge
2 → 1    1 edge
1 → 3    1 edge

Total:

3 edges

And:

leftDepth + rightDepth
= 2 + 1
= 3

Therefore:

self.res = max(
    self.res,
    leftDepth + rightDepth
)

The longest path does not necessarily pass through the root.

For example:

The longest path may pass through node 2 rather than using the root as its highest point.

Therefore, at every node, we calculate:

leftDepth + rightDepth

and compare it with the current global maximum:

self.res = max(
    self.res,
    leftDepth + rightDepth
)

So self.res represents:

The maximum diameter found anywhere in the tree so far.

This is the most important part of the problem.

When calculating the diameter at the current node, we can use both sides:

left → node → right

So:

leftDepth + rightDepth

can be used to update the global answer.

However, when returning a depth to the parent, we cannot return both sides.

Suppose:

           parent
             |
            node
           /    \
        left    right

If node returned both sides to parent, the structure would become:

           parent
             |
            node
           /    \
        left    right

This is a Y-shaped structure.

It is not a single path because it branches.

Therefore, when returning to the parent, we must choose only one side:

node → left

or:

node → right

We choose the deeper one:

return 1 + max(leftDepth, rightDepth)

This is the core idea of LeetCode 543.

Update the Diameter¶

At the current node, both sides can be used:

left → node → right

Therefore:

self.res = max(
    self.res,
    leftDepth + rightDepth
)

Return to Parent¶

When returning upward, only one side can be used:

node → left

or:

node → right

Therefore:

return 1 + max(leftDepth, rightDepth)

Consider:

Initially:

self.res = 0

Node `4`¶

Node 4 is a leaf.

leftDepth = 0
rightDepth = 0

Update diameter:

0 + 0 = 0

So:

res = 0

Return depth:

1 + max(0, 0) = 1

Node `5`¶

Same:

leftDepth = 0
rightDepth = 0

Update:

res = 0

Return:

Node `2`¶

Now:

leftDepth = 1
rightDepth = 1

The complete path passing through 2 is:

4 → 2 → 5

Diameter:

leftDepth + rightDepth
= 1 + 1
= 2

Update:

res = 2

Return to node 1:

1 + max(1, 1)
= 2

This represents the depth:

2 → 4

or:

2 → 5

Node `3`¶

Node 3 is a leaf.

Return:

Node `1`¶

Now:

leftDepth = 2
rightDepth = 1

The complete path can be:

4 → 2 → 1 → 3

Diameter:

2 + 1 = 3

Update:

res = 3

Finally:

Output = 3

For every node:

            node
           /    \
        left    right

           ↓

Calculate:

leftDepth = traverse(left)
rightDepth = traverse(right)

           ↓

Complete path through current node:

leftDepth + rightDepth

           ↓

Update global diameter:

res = max(res, leftDepth + rightDepth)

           ↓

Return one branch to parent:

1 + max(leftDepth, rightDepth)

LeetCode 543 and LeetCode 124 have almost exactly the same recursive structure.

LeetCode 124 — Maximum Path Sum¶

Update global answer:

self.res = max(
    self.res,
    node.val + left + right
)

Return to parent:

return node.val + max(left, right)

LeetCode 543 — Diameter¶

Update global answer:

self.res = max(
    self.res,
    leftDepth + rightDepth
)

Return to parent:

return 1 + max(leftDepth, rightDepth)

So both problems follow the same pattern:

Update global answer
→ Both left and right can be used

Return to parent
→ Only one side can be used

Time Complexity¶

Each node is visited exactly once:

O(n)

where n is the number of nodes.

Space Complexity¶

The recursion stack depends on the height of the tree:

O(h)

For a balanced tree:

O(log n)

For a completely skewed tree:

O(n)

The most important distinction is:

What do we use to update the answer?

leftDepth + rightDepth

because the complete path can go:

left → node → right

But:

What do we return to the parent?

1 + max(leftDepth, rightDepth)

because a path returned to the parent cannot branch.

The easiest way to remember LeetCode 543 is:

Update answer → use both sides

Return upward → use one side

or simply:

# complete path
self.res = max(self.res, leftDepth + rightDepth)

# one-sided depth
return 1 + max(leftDepth, rightDepth)

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 14, 2026

Python solution¶

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

        self.traverse(root)

        return self.res

    def traverse(self, node):
        if not node:
            return 0

        leftDepth = self.traverse(node.left)
        rightDepth = self.traverse(node.right)

        self.res = max(
            self.res,
            leftDepth + rightDepth
        )

        return 1 + max(leftDepth, rightDepth)

Back to Bonus Binary Tree · All Algorithm notes

543. Diameter of Binary Tree¶

Problem¶

Example¶

Update the Diameter¶

Return to Parent¶

Node 4¶

Node 5¶

Node 2¶

Node 3¶

Node 1¶

LeetCode 124 — Maximum Path Sum¶

LeetCode 543 — Diameter¶

Time Complexity¶

Space Complexity¶

Python solution¶

Node `4`¶

Node `5`¶

Node `2`¶

Node `3`¶

Node `1`¶