Diameter of Binary Tree in DSA Go

Mental Model

The diameter is the longest path between any two nodes in a tree, which may or may not pass through the root.

Analogy: Imagine a tree as a network of roads connecting cities; the diameter is the longest possible route you can take between two cities without repeating roads.

      1
     / \
    2   3
   / \
  4   5

Diameter could be path 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Find the longest path between any two nodes in the tree

Step 1: Start at node 4, calculate height = 1 (leaf node)

Node 4: height=1, diameter=0

Why: Leaf nodes have height 1 and no diameter path inside

Step 2: Start at node 5, calculate height = 1 (leaf node)

Node 5: height=1, diameter=0

Why: Leaf nodes have height 1 and no diameter path inside

Step 3: At node 2, calculate height = max(1,1)+1=2; diameter through 2 = 1+1=2

Node 2: height=2, diameter=2 (path 4 -> 2 -> 5)

Why: Diameter through node 2 is sum of left and right heights

Step 4: At node 3, height = 1 (leaf), diameter=0

Node 3: height=1, diameter=0

Why: Leaf node height and diameter

Step 5: At root node 1, height = max(2,1)+1=3; diameter through 1 = 2+1=3

Node 1: height=3, diameter=3 (path 4 -> 2 -> 1 -> 3)

Why: Diameter through root is sum of left and right heights

Result:

Diameter = 3 (longest path: 4 -> 2 -> 1 -> 3)

Annotated Code

DSA Go

package main

import "fmt"

// TreeNode represents a node in the binary tree
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// diameterOfBinaryTree returns the diameter of the binary tree
func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0

    // height calculates height of node and updates maxDiameter
    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftHeight := height(node.Left) // height of left subtree
        rightHeight := height(node.Right) // height of right subtree

        // diameter through current node is sum of left and right heights
        if leftHeight+rightHeight > maxDiameter {
            maxDiameter = leftHeight + rightHeight
        }

        // height of current node is max of left/right heights plus 1
        return max(leftHeight, rightHeight) + 1
    }

    height(root)
    return maxDiameter
}

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

func main() {
    // Construct the tree:
    //      1
    //     / \
    //    2   3
    //   / \
    //  4   5
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 4}
    root.Left.Right = &TreeNode{Val: 5}

    diameter := diameterOfBinaryTree(root)
    fmt.Println(diameter)
}

if node == nil { return 0 }

base case: empty node has height 0

leftHeight := height(node.Left)

recursively find left subtree height

rightHeight := height(node.Right)

recursively find right subtree height

if leftHeight+rightHeight > maxDiameter { maxDiameter = leftHeight + rightHeight }

update max diameter if path through current node is longer

return max(leftHeight, rightHeight) + 1

return height of current node for parent's calculation

Output

3

Complexity Analysis

Time: O(n) because each node is visited once during height calculation

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach might compute height repeatedly causing O(n^2) time; this approach computes height and diameter in one pass

Edge Cases

Empty tree (root is nil)

Returns diameter 0 as there are no nodes

DSA Go

if node == nil { return 0 }

Single node tree

Diameter is 0 because no edges exist

DSA Go

if node == nil { return 0 }

Skewed tree (all nodes only on one side)

Diameter equals number of edges in the longest path (height - 1)

DSA Go

if leftHeight+rightHeight > maxDiameter { maxDiameter = leftHeight + rightHeight }

When to Use This Pattern

When asked for longest path between any two nodes in a tree, use diameter pattern by combining heights of left and right subtrees at each node.

Common Mistakes

Mistake: Calculating diameter as height of left subtree plus height of right subtree only at root node
Fix: Calculate diameter at every node during height calculation to find global maximum

Summary

Finds the longest path between any two nodes in a binary tree.

Use when you need the maximum distance between any two nodes, not just from root.

The diameter is the largest sum of left and right subtree heights at any node.