Diameter of N-Ary Tree - Practice Coding Problems

Diameter of N-Ary Tree - Problem

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

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

Input & Output

Example 1 — Standard N-ary Tree

$ Input: root = [1,null,3,2,4,null,5,6]

› Output: 3

💡 Note: The longest path is from node 5 → 3 → 1 → 2, which has 3 edges. The diameter passes through the root node 1.

Example 2 — Single Node

$ Input: root = [1]

› Output: 0

💡 Note: A single node has no edges, so the diameter is 0.

Example 3 — Linear Tree

$ Input: root = [1,null,2,null,3,null,4]

› Output: 3

💡 Note: The tree forms a linear chain: 1 → 2 → 3 → 4. The diameter is the path from 1 to 4, which has 3 edges.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
0 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Tree

N-ary tree with nodes and edges

Find Paths

Identify all possible paths between node pairs

Maximum Length

Return length of longest path (number of edges)

Key Takeaway

🎯 Key Insight: The diameter is the sum of the two deepest subtree heights at any node

Asked in

G Google 45 F Facebook 38 A Amazon 32 M Microsoft 28

The optimal approach uses DFS to calculate subtree heights while tracking the maximum diameter. For each node, the diameter passing through it equals the sum of its two deepest child subtree heights. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Paths	O(n²)	O(h)	For each node, find all paths and track the maximum length
DFS with Height Calculation	O(n)	O(h)	Single DFS pass calculating diameter using subtree heights

Brute Force - Check All Paths — Algorithm Steps

For each node, perform DFS to find distances to all other nodes
Track the maximum distance found across all pairs
Return the global maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Nodes

Gather all nodes in the tree

Check Pairs

Calculate distance between each pair

Find Maximum

Track the longest distance found

Code -

solution.c — C

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

struct Node {
    int val;
    struct Node** children;
    int childCount;
};

struct Node* createNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->children = NULL;
    node->childCount = 0;
    return node;
}

int getAllNodes(struct Node* node, struct Node** nodes, int* count) {
    if (!node) return 0;
    
    nodes[(*count)++] = node;
    for (int i = 0; i < node->childCount; i++) {
        getAllNodes(node->children[i], nodes, count);
    }
    return *count;
}

int getDistance(struct Node* start, struct Node* target, struct Node* parent) {
    if (start == target) return 0;
    
    for (int i = 0; i < start->childCount; i++) {
        if (start->children[i] != parent) {
            int dist = getDistance(start->children[i], target, start);
            if (dist != -1) return dist + 1;
        }
    }
    return -1;
}

int solution(struct Node* root) {
    if (!root) return 0;
    
    struct Node* allNodes[1000];
    int nodeCount = 0;
    getAllNodes(root, allNodes, &nodeCount);
    
    int maxDiameter = 0;
    for (int i = 0; i < nodeCount; i++) {
        for (int j = i + 1; j < nodeCount; j++) {
            int distance = getDistance(allNodes[i], allNodes[j], NULL);
            if (distance > maxDiameter) {
                maxDiameter = distance;
            }
        }
    }
    
    return maxDiameter;
}

int main() {
    char input[1000];
    fgets(input, sizeof(input), stdin);
    
    struct Node* root = createNode(1);
    struct Node* child1 = createNode(3);
    struct Node* child2 = createNode(2);
    struct Node* child3 = createNode(4);
    
    root->children = (struct Node**)malloc(3 * sizeof(struct Node*));
    root->children[0] = child1;
    root->children[1] = child2;
    root->children[2] = child3;
    root->childCount = 3;
    
    child1->children = (struct Node**)malloc(2 * sizeof(struct Node*));
    child1->children[0] = createNode(5);
    child1->children[1] = createNode(6);
    child1->childCount = 2;
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we traverse the entire tree to find distances

⚠ Quadratic Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

89.4K Views

Medium Frequency

~25 min Avg. Time

1.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 - Check All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler