Sign in
Skip to solution
mediumDSA

How do you compute the diameter of a binary tree?

751 views
01

Understand the problem

Explain tree diameter.

treesrecursion
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

The diameter is the longest path between any two nodes. For each node, the candidate is leftHeight + rightHeight; recurse returning heights while tracking the global max. O(n), computing height and diameter in one pass to avoid O(n²).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Height + global best
Run Playground
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def diameter_of_binary_tree(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        lh = height(node.left)
        rh = height(node.right)
        best = max(best, lh + rh)        # path through this node
        return 1 + max(lh, rh)
    height(root)
    return best


# --- demo ---  longest path 4->2->1->3->5 = 4 edges
root = TreeNode(1, TreeNode(2, TreeNode(4), None), TreeNode(3, None, TreeNode(5)))
print(diameter_of_binary_tree(root))   # 4
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 51 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track