543. Diameter of Binary Tree

At a Glance

• Topic: trees
• Pattern: Tree DFS (DP on tree)
• Difficulty: Easy
• Companies: Amazon, Google, Meta, Apple, Microsoft
• Frequency: High
• LeetCode: 543

Problem (one-liner)

Given the root of a binary tree, return the length of the longest path between any two nodes in the tree. The path may or may not pass through the root; length is the number of edges on that path.

Recognition Cues

• "Diameter" / longest path in an undirected view of the tree
• Path through a node uses one height left + one height right
• Often paired with computing subtree height in one pass

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n²) time — for each node, compute heights of left and right naively with repeated traversals.
• Better — O(n) time / O(n) space — two DFS passes (still suboptimal constant factors).
• Optimal — O(n) time / O(h) stack — one post-order pass: at each node, diameterThroughNode = leftHeight + rightHeight, update global max; return max(leftHeight, rightHeight) + 1 to parent.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func diameterOfBinaryTree(root *TreeNode) int {
	best := 0
	var height func(*TreeNode) int
	height = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		leftHeight := height(node.Left)
		rightHeight := height(node.Right)
		candidate := leftHeight + rightHeight
		if candidate > best {
			best = candidate
		}
		if leftHeight > rightHeight {
			return 1 + leftHeight
		}
		return 1 + rightHeight
	}
	height(root)
	return best
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function diameterOfBinaryTree(root) {
	let best = 0;
	function height(node) {
		if (node === null) {
			return 0;
		}
		const leftHeight = height(node.left);
		const rightHeight = height(node.right);
		best = Math.max(best, leftHeight + rightHeight);
		return 1 + Math.max(leftHeight, rightHeight);
	}
	height(root);
	return best;
}

Walkthrough

Tree: 1 / 2,3 / 4,5

Answer: 3 edges (path through 4–2–5 or 4–2–1–3 depending on shape; longest here 4–2–1–3 is 3 edges).

Invariant: height returns the longest root-to-leaf edge count below node; each combine step records best path that turns at node.

Edge Cases

• Two nodes only → diameter 1
• Skewed tree → diameter can be n-1 edges along the spine
• null root → 0

Pitfalls

• Counting nodes instead of edges (problem wants edges)
• Using diameter leftHeight + rightHeight + 1 (that would be node count style—wrong here)

Similar Problems

• 104. Maximum Depth of Binary Tree — same height subroutine without global best.
• 110. Balanced Binary Tree — height with constraint check at each node.
• 437. Path Sum III — another “path in tree” aggregate with prefix ideas.

Variants

• Longest path between any two leaves only (must exclude paths ending at internal nodes if defined that way).
• Weighted edges → replace +1 with edge weight when accumulating.

Mind-Map Tags

#trees #dp-on-tree #post-order #diameter #global-best