Diameter of Binary Tree

Problem statement

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

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example:

Input:

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

Expected output:

3

Explanation: The longest path is 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3 (3 edges).

If you would like to solve the problem on LeetCode, here is the link to the problem: LeetCode problem link

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
}