Diameter of Binary Tree

Problem statement

In a binary tree, the diameter is the longest path between any two nodes, measured in edges. The path does not have to include the root. Return that edge count.

Example:

Input:

root = [1, 2, 3, 4, 5]

Expected output:

3

Why: paths like 4-2-1-3 use three edges.

Practice on LeetCode: Diameter of Binary Tree

Golang Solution

Run a DFS that returns the height of each subtree. At every node, the path that goes left → node → right has length leftHeight + rightHeight. Track the maximum of those path lengths as the diameter. Each call returns 1 + max(left, right) so parents can build their heights.

Time: O(n) — each node visited once
Space: O(h) — recursion stack (h = tree height)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    diameter := 0

    var dfs func(root *TreeNode) int

    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }

        left := dfs(root.Left)
        right := dfs(root.Right)

        if diameter < (left + right) {
            diameter = left + right
        }

        if left > right {
            return left + 1
        }

        return right + 1
    }

    dfs(root)

    return diameter
}