Diameter of Binary Tree

1. Problem Description

Given a binary tree, calculate its diameter. The diameter of a binary tree is the maximum path length between any two nodes. This path may or may not pass through the root.

2. Approach

1. Approach 1
   • The diameter can be viewed as the number of nodes on the path minus 1
   • The number of nodes on such a path can be calculated as 1 + left-subtree depth + right-subtree depth
   • The depth can be computed with DFS

3. Implementation

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

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

    leftHeight := getHeight(root.Left)
    rightHeight := getHeight(root.Right)

    *maxVal = max(*maxVal, leftHeight + rightHeight)
    dfs(root.Left, maxVal)
    dfs(root.Right, maxVal)

}

func getHeight(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(getHeight(root.Left), getHeight(root.Right))
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. References

• 543. Diameter of Binary Tree - LeetCode