Tree Diameter - Practice Coding Problems

Tree Diameter - Problem

Tree Depth-First Search Breadth-First Search Graph Topological Sort Medium

The diameter of a tree is the number of edges in the longest path in that tree. There is an undirected tree of n nodes labeled from 0 to n - 1.

You are given a 2D array edges where edges.length == n - 1 and edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the tree.

Return the diameter of the tree.

Input & Output

Example 1 — Linear Tree

$ Input: edges = [[0,1],[1,2],[2,3],[1,4]]

› Output: 3

💡 Note: The tree forms a shape where longest path is from node 4 to node 3 (or 3 to 4), going through nodes 4→1→2→3, which has 3 edges.

Example 2 — Simple Path

$ Input: edges = [[0,1],[0,2]]

› Output: 2

💡 Note: Tree with 3 nodes: 1-0-2. The diameter is the path from node 1 to node 2, which has 2 edges (1→0→2).

Example 3 — Single Edge

$ Input: edges = [[0,1]]

› Output: 1

💡 Note: Tree with only 2 nodes connected by 1 edge. The diameter is simply that one edge.

Constraints

n == edges.length + 1
1 ≤ n ≤ 10⁴
0 ≤ a_i, b_i < n
a_i ≠ b_i
The given input represents a valid tree.

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Given edges representing connections between nodes

Find Longest Path

Identify the path with maximum number of edges

Count Edges

Return the number of edges in longest path

Key Takeaway

🎯 Key Insight: Use two DFS/BFS traversals to efficiently find tree diameter in O(n) time

Asked in

f Facebook 15 a Amazon 12 G Google 8 M Microsoft 6

The key insight is that the longest path in a tree always connects two leaf nodes, and we can find it efficiently using two DFS/BFS traversals. The optimal approach runs DFS from any node to find one endpoint, then DFS from that endpoint to find the diameter. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - DFS from Every Node	O(n²)	O(n)	Run DFS from each node to find maximum distance
Two BFS - Level-Order Approach	O(n)	O(n)	Use BFS twice to find diameter endpoints
Two DFS - Optimal Tree Diameter	O(n)	O(n)	Find farthest node twice to get diameter endpoints

Brute Force - DFS from Every Node — Algorithm Steps

Build adjacency list from edges
For each node, run DFS to find max distance
Track the overall maximum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from edges

DFS from Each Node

Run DFS from every node to find max distance

Track Maximum

Keep track of the overall maximum distance

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 10000

int graph[MAX_NODES][MAX_NODES];
int graph_size[MAX_NODES];
int visited[MAX_NODES];

int dfs(int node, int parent, int n) {
    int maxDist = 0;
    for (int i = 0; i < graph_size[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            int dist = 1 + dfs(neighbor, node, n);
            if (dist > maxDist) {
                maxDist = dist;
            }
        }
    }
    return maxDist;
}

int solution(int edges[][2], int edgesSize) {
    if (edgesSize == 0) return 0;
    
    // Initialize graph
    memset(graph_size, 0, sizeof(graph_size));
    int nodes[MAX_NODES];
    int nodeCount = 0;
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graph_size[u]++] = v;
        graph[v][graph_size[v]++] = u;
        
        // Track unique nodes
        int found_u = 0, found_v = 0;
        for (int j = 0; j < nodeCount; j++) {
            if (nodes[j] == u) found_u = 1;
            if (nodes[j] == v) found_v = 1;
        }
        if (!found_u) nodes[nodeCount++] = u;
        if (!found_v) nodes[nodeCount++] = v;
    }
    
    int maxDiameter = 0;
    for (int i = 0; i < nodeCount; i++) {
        int dist = dfs(nodes[i], -1, nodeCount);
        if (dist > maxDiameter) {
            maxDiameter = dist;
        }
    }
    
    return maxDiameter;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse 2D array manually
    int edges[1000][2];
    int edgesSize = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                int u = 0, v = 0;
                while (*ptr && *ptr != ',' && *ptr != ']') {
                    u = u * 10 + (*ptr - '0');
                    ptr++;
                }
                if (*ptr == ',') ptr++;
                while (*ptr && *ptr != ']') {
                    v = v * 10 + (*ptr - '0');
                    ptr++;
                }
                edges[edgesSize][0] = u;
                edges[edgesSize][1] = v;
                edgesSize++;
                if (*ptr == ']') ptr++;
            } else {
                ptr++;
            }
        }
    }
    
    printf("%d\n", solution(edges, edgesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform DFS which visits all n nodes

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list storage and recursion stack depth up to n

⚡ Linearithmic Space

89.4K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - DFS from Every Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler