Diameter of Binary Tree

Easy

The problem

The diameter is the number of edges on the longest path between any two nodes in the tree. The path may or may not go through the root. Return that length.

Example 1
Input: root = [1, 2, 3, 4, 5]
Output: 3
The path 4 → 2 → 1 → 3 uses 3 edges. 5 → 2 → 1 → 3 is just as long.
Example 2
Input: root = [1, 2]
Output: 1

Limits

1 ≤ number of nodes ≤ 10,000
Count edges (the lines between nodes), not nodes

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The longest path through a node is its left height plus its right height. The best path may not touch the root.

The idea

DFS returns the height; at every node update a global best with leftHeight + rightHeight.

Target: O(n) time, O(h) space

Go function shape

func diameterOfBinaryTree(root *TreeNode) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// DiameterOfBinaryTree: global-variable style.
// The function RETURNS the height (what the parent needs) but RECORDS the best
// bend through this node in an outer variable (what the question asks).
func DiameterOfBinaryTree(root *TreeNode) int {
	best := 0
	var height func(n *TreeNode) int
	height = func(n *TreeNode) int {
		if n == nil {
			return 0
		}
		l, r := height(n.Left), height(n.Right)
		best = max(best, l+r) // path bending at n uses both sides
		return 1 + max(l, r)
	}
	height(root)
	return best
}

Read the lesson: Trees: BFS / DFS