Calculating the Diameter of a Binary Tree in C#

Binary trees, one interesting problem is finding the diameter of the tree. The diameter is defined as the length of the longest path between any two nodes in the tree. This can be measured either as the number of nodes or the number of edges along the path.

Understanding the Tree Diameter

Consider the following binary tree:

      1
     / \
    2   3
   / \
  4   5

• The diameter in nodes: 4 (path: 4 → 2 → 1 → 3)

• The diameter in edges: 3

Notice that the longest path does not necessarily pass through the root.

Recursive Approach

To compute the diameter efficiently:

1. Traverse the tree using DFS (Depth-First Search).

2. For each node, compute the height of its left and right subtrees.

3. The longest path through that node is leftHeight + rightHeight + 1 (in nodes) or leftHeight + rightHeight (in edges).

4. Keep track of the maximum diameter found.

This approach runs in O(n) time, visiting each node only once.

C# Implementation

using System;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class BinaryTree
{
    private int maxDiameter = 0;

    public int Diameter(TreeNode root, bool countEdges = false)
    {
        maxDiameter = 0;
        Height(root);
        return countEdges ? Math.Max(0, maxDiameter - 1) : maxDiameter;
    }

    private int Height(TreeNode node)
    {
        if (node == null)
            return 0;

        int leftHeight = Height(node.left);
        int rightHeight = Height(node.right);

        int pathThroughNode = leftHeight + rightHeight + 1; // nodes
        maxDiameter = Math.Max(maxDiameter, pathThroughNode);

        return Math.Max(leftHeight, rightHeight) + 1;
    }
}

Example Usage

class Program
{
    static void Main()
    {
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n2 = new TreeNode(2, n4, n5);
        TreeNode n3 = new TreeNode(3);
        TreeNode n1 = new TreeNode(1, n2, n3);

        BinaryTree tree = new BinaryTree();
        Console.WriteLine("Diameter in nodes: " + tree.Diameter(n1));          // Output: 4
        Console.WriteLine("Diameter in edges: " + tree.Diameter(n1, true));    // Output: 3
    }
}

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes. Each node is visited once.

• Space Complexity: O(h), due to recursion stack, where h is the height of the tree. In the worst case (skewed tree), h = n.

Calculating the diameter of a binary tree is a common problem in interviews and coding exercises. Using a single DFS traversal allows for an efficient O(n) solution. This C# implementation can be easily adapted to return the actual path as well, not just its length.