1522. Diameter of N-Ary Tree
Problem Description
The problem involves finding the diameter of an N-ary tree. The diameter is defined as the length (number of edges) of the longest path between any two nodes within the tree. A key point to note is that this path is not required to go through the tree's root. Understanding how to handle N-ary trees, which are trees where a node can have any number of children, is crucial in solving this problem. Level order traversal serialization (where each group of children is separated by the null value) is used for input representation.
Flowchart Walkthrough
Here's an analysis for solving the problem LeetCode 1522. Diameter of N-ary Tree using the Flowchart. Let’s walk through the decision flow to determine the appropriate algorithm:
Is it a graph?
- Yes: The N-ary tree can be considered as a special type of graph.
Is it a tree?
- Yes: An N-ary tree is, by definition, a tree.
DFS
- As the problem is about finding the diameter of the N-ary tree, and since we have determined that this structure is a tree, the recommended approach based on the flowchart leads us to use Depth-First Search (DFS). DFS is particularly suited for tree traversals and exploring all possible paths, which is essential for calculating the diameter (the longest path between any two nodes).
Conclusion: From the flowchart, Depth-First Search is the suggested method for handling trees, especially when it comes to tasks like calculating the diameter which involves traversing all nodes and finding maximum depths from each node.
Intuition
When finding the diameter of an N-ary tree, a depth-first search (DFS) approach can be applied effectively. The diameter of the tree could potentially be the distance between two nodes that are below the root of the tree, which means it might not include the root itself. Therefore, for each node, we need to consider the two longest paths that extend from this node down its children, because these paths could potentially contribute to the maximum diameter if they are connected through the current node.
To implement this, we use a recursive DFS function that computes and returns the height of the current subtree while simultaneously calculating the potential diameter that passes through the current node (the sum of the two longest child paths connected at the node). We track the overall longest path seen so far with a nonlocal variable 'ans', which gets updated when a larger diameter is found.
The key steps in our approach are:
- Traverse each node with DFS, starting from the root.
- For each node visited, calculate the lengths of the longest (max) and second-longest (smax) paths among its child nodes.
- Update the overall potential diameter 'ans' if the sum of max and smax is greater than the current 'ans'.
- At each node, return the height of this subtree to its parent, which is 1 plus the longest path length among the child nodes.
By doing this for each node, once the traversal is complete, 'ans' will hold the length of the longest path, which is the diameter of the N-ary tree.
Learn more about Tree and Depth-First Search patterns.
Solution Approach
The solution approach for calculating the diameter of an N-ary tree involves a depth-first search (DFS) algorithm. The DFS is customized to perform two operations at once – calculate the height of the current subtree and use this information to evaluate the longest path that passes through each node (potential diameters).
Here's a step-by-step breakdown of the implementation using the provided solution code:
-
We define a DFS helper function
dfs
that takes a node of the tree as an argument. This function returns the height of the tree rooted at the given node. -
Inside the
dfs
function:-
We start by checking if the current
root
node isNone
(base case). If it is, we return 0 since a non-existent node does not contribute to height or diameter. -
We then introduce two variables
m1
andm2
initialized to 0, which will store the lengths of the longest (m1
) and second-longest (m2
) paths found within the children of the current node. -
We loop through each child of the current node and recursively call
dfs(child)
. The returned valuet
is the height of the subtree rooted atchild
. We use this value to potentially updatem1
andm2
.-
If
t
is greater thanm1
, we setm2
tom1
and thenm1
tot
, thus keepingm1
as the max height andm2
as the second max height among the children. -
If
t
is not greater thanm1
but is greater thanm2
, we updatem2
witht
.
-
-
After considering all children, we update the
ans
variable (which is kept in the outer scope ofdfs
and declared asnonlocal
) with the maximum of its current value and the sum ofm1 + m2
, representing the potential diameter at this node (the longest path through the node).
-
-
The
dfs
function concludes by returning1 + m1
, which represents the height of the subtree rooted at the current node (1 for the edge connecting to its parent andm1
as the height of its longest subtree). -
In the
diameter
method of theSolution
class, we initialize theans
variable to 0 (to globally keep track of the longest path seen) and calldfs(root)
to kick off the recursive DFS from the root of the tree. -
Finally, the
diameter
method returns theans
variable, which now contains the diameter of the tree.
The use of recursion to traverse the tree, combined with updating the two longest paths at each node, harnesses the depth-first search pattern efficiently to solve the problem of finding the tree's diameter.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have an N-ary tree represented using level order serialization as follows:
1 / | \ 2 3 4 / | \ 5 6 7
We want to find the diameter of this tree, which is the longest path between any two nodes. We will walk through the DFS approach using the provided solution template:
-
We start the DFS with the
root
, which is node 1. We initializeans
to 0. Thedfs
function will traverse the tree and track the longest path at each node. -
When we process the
root
(node 1), we initializem1
andm2
both to 0. These variables will track the longest and second-longest heights among the children of each node. -
We recursively call
dfs
for each child of theroot
.- For child node 2, the recursive call to
dfs
returns 1 (since node 5 is its only child and adds one edge to the height). - For child node 3, the recursive call to
dfs
returns 0 (as it has no child). - For child node 4, the DFS must consider both children. Nodes 6 and 7 contribute a height of 1 each, and since these are the longest and second-longest heights for this subtree, after considering both, node 4 returns 2 as the height (1 for the longest child plus 1 for the edge to node 4).
- For child node 2, the recursive call to
-
Now, with the heights from the children of the
root
, we updatem1
andm2
for theroot
.m1
becomes 2 (from node 4), andm2
becomes 1 (from node 2). Therefore, the potential diameter passing throughroot
at this stage ism1 + m2 = 2 + 1 = 3
. We updateans
to 3. -
The DFS continues recursively for all nodes but finds no longer path than the current
ans
. -
After the DFS is complete and all nodes have been visited,
ans
holds the diameter of the tree. In this case, it remains 3, representing the length of the longest path, which happens to be from node 5 to node 7 via theroot
(5 -> 2 -> 1 -> 4 -> 6 or 7). -
The
diameter
method then returnsans
, which is 3, as the diameter of the tree.
This walkthrough illustrates the algorithm's efficiency in computing the diameter by determining the longest path through each node without necessarily passing through the root.
Solution Implementation
1# Definition for a Node.
2class Node:
3 def __init__(self, val=None, children=None):
4 self.val = val
5 self.children = children if children is not None else []
6
7class Solution:
8 def diameter(self, root: 'Node') -> int:
9 # Helper function to perform depth-first search
10 def dfs(node: 'Node') -> int:
11 # base case: if the current node is None, return 0
12 if node is None:
13 return 0
14 # accessing the non-local variable 'max_diameter' to update its value within this helper function
15 nonlocal max_diameter
16 # initialize the two longest paths from the current node to 0
17 longest_path = second_longest_path = 0
18 # iterate over all the children of the current node
19 for child in node.children:
20 # recursively find the longest path for each child
21 path_length = dfs(child)
22 # check if the current path is longer than the longest recorded path
23 if path_length > longest_path:
24 # update the second longest and longest paths accordingly
25 second_longest_path, longest_path = longest_path, path_length
26 # else if it's only longer than the second longest, update the second longest
27 elif path_length > second_longest_path:
28 second_longest_path = path_length
29 # update the maximum diameter encountered so far based on the two longest paths from this node
30 max_diameter = max(max_diameter, longest_path + second_longest_path)
31 # return the longer path increased by 1 for the edge between this node and its parent
32 return 1 + longest_path
33
34 # Initialize max_diameter to 0 before starting DFS
35 max_diameter = 0
36 # Call the dfs function starting from the root node
37 dfs(root)
38 # Once DFS is complete, return the max_diameter found
39 return max_diameter
40
1/**
2 * Definition for a N-ary tree node.
3 */
4class Node {
5 public int val;
6 public List<Node> children;
7
8 // Constructor initializes value and empty children list
9 public Node() {
10 children = new ArrayList<Node>();
11 }
12
13 // Constructor initializes node with a value and empty children list
14 public Node(int val) {
15 this.val = val;
16 children = new ArrayList<Node>();
17 }
18
19 // Constructor initializes node with a value and given children list
20 public Node(int val, ArrayList<Node> children) {
21 this.val = val;
22 this.children = children;
23 }
24}
25
26public class Solution {
27 // This class variable keeps track of the diameter of the tree
28 private int diameter;
29
30 /**
31 * Computes the diameter of an N-ary tree.
32 * The diameter of an N-ary tree is the length of the longest path between any two nodes in a tree.
33 *
34 * @param root the root node of the tree
35 * @return the diameter of the tree
36 */
37 public int diameter(Node root) {
38 diameter = 0;
39 depthFirstSearch(root);
40 return diameter;
41 }
42
43 /**
44 * Uses Depth First Search (DFS) to find the length of the longest path through the N-ary tree from the current node.
45 *
46 * @param root the current node being traversed
47 * @return the maximum depth emanating from the current node
48 */
49 private int depthFirstSearch(Node root) {
50 // Leaf nodes have a depth of 0
51 if (root == null) {
52 return 0;
53 }
54
55 int maxDepth1 = 0; // Tracks the longest path
56 int maxDepth2 = 0; // Tracks the second longest path
57
58 // Recursively obtain the depth for children nodes to find the longest paths
59 for (Node child : root.children) {
60 int depth = depthFirstSearch(child);
61
62 // Check and set the longest and second-longest distances found
63 if (depth > maxDepth1) {
64 maxDepth2 = maxDepth1;
65 maxDepth1 = depth;
66 } else if (depth > maxDepth2) {
67 maxDepth2 = depth;
68 }
69 }
70
71 // Update the diameter if the sum of two longest paths through the current node is greater than the current diameter
72 diameter = Math.max(diameter, maxDepth1 + maxDepth2);
73
74 // Return the maximum depth plus one for the current path
75 return 1 + maxDepth1;
76 }
77}
78
1// Definition for a Node is provided as per the question context
2class Node {
3public:
4 int val; // The value contained within the node.
5 vector<Node*> children; // A vector containing pointers to its children.
6
7 Node() {}
8
9 Node(int _val) {
10 val = _val;
11 }
12
13 Node(int _val, vector<Node*> _children) {
14 val = _val;
15 children = _children;
16 }
17};
18
19class Solution {
20public:
21 int maxDiameter; // Class variable to store the maximum diameter found.
22
23 // Public method which is the starting point for finding the diameter of the tree.
24 int diameter(Node* root) {
25 maxDiameter = 0; // Initialize the max diameter to 0.
26 dfs(root); // Call the depth-first search helper method.
27 return maxDiameter; // Return the maximum diameter calculated.
28 }
29
30 // Private helper method for DFS traversal which calculates the depths and updates the diameter.
31 // It returns the maximum depth from the current node to its furthest leaf node.
32 int dfs(Node* root) {
33 if (!root) return 0; // Base case: If the node is null, return 0 (no depth).
34
35 int maxDepth1 = 0; // To store the maximum length of the paths in the children.
36 int maxDepth2 = 0; // To store the second maximum length of the paths in the children.
37
38 // Iterate through each child node of the current root.
39 for (Node* child : root->children) {
40 int depth = dfs(child); // Recursive call to get the depth for each child.
41 // Update the two maximum depths found among children nodes
42 if (depth > maxDepth1) {
43 maxDepth2 = maxDepth1; // Update the second max if the new max is found
44 maxDepth1 = depth; // Update the new max depth
45 } else if (depth > maxDepth2) {
46 maxDepth2 = depth; // Update the second max if greater than it but less than the max depth
47 }
48 }
49
50 // Update the maximum diameter if the sum of the two largest depths is greater than the current diameter.
51 maxDiameter = max(maxDiameter, maxDepth1 + maxDepth2);
52
53 // Return the maximum depth of this subtree to its parent caller, which is 1 plus the max depth of its children.
54 return 1 + maxDepth1;
55 }
56};
57
1// Define the type for a Node that includes a value and an array of Node references as children
2type Node = {
3 val: number;
4 children: Node[];
5};
6
7let maxDiameter: number; // Global variable to store the maximum diameter found.
8
9// This function is the entry point for finding the diameter of the n-ary tree.
10function diameter(root: Node | null): number {
11 maxDiameter = 0; // Initialize the max diameter to 0.
12 dfs(root); // Call the depth-first search helper function.
13 return maxDiameter; // Return the maximum diameter calculated.
14}
15
16// Helper function for DFS traversal that calculates depths and updates the diameter.
17// It returns the maximum distance from the current node to its furthest leaf node.
18function dfs(root: Node | null): number {
19 if (root === null) return 0; // Base case: If the node is null, return 0 (no depth).
20
21 let maxDepthOne = 0; // To store the maximum depth among the paths in the children.
22 let maxDepthTwo = 0; // To store the second maximum depth among the paths in the children.
23
24 // Iterate through each child node of the current root.
25 for (let child of root.children) {
26 let depth = dfs(child); // Recursive call to get the depth for each child.
27 // Update the two maximum depths found among children nodes
28 if (depth > maxDepthOne) {
29 maxDepthTwo = maxDepthOne; // Second max updated if a new max is found
30 maxDepthOne = depth; // Set as the new max depth
31 } else if (depth > maxDepthTwo) {
32 maxDepthTwo = depth; // Update the second max if it's greater than the current second max
33 }
34 }
35
36 // Update the maximum diameter if the sum of the two largest depths is greater than the current maximum diameter.
37 maxDiameter = Math.max(maxDiameter, maxDepthOne + maxDepthTwo);
38
39 // Return the maximum depth of this subtree to its parent, which is 1 plus the maximum depth of its children.
40 return 1 + maxDepthOne;
41}
42
Time and Space Complexity
The code provided defines a function dfs(root)
that is used to compute the diameter of an N-ary tree. The diameter of an N-ary tree is defined as the length of the longest path between any two nodes in the tree.
Time Complexity:
The time complexity of the provided code is O(N)
, where N
is the total number of nodes in the tree. This is because the dfs()
function is called recursively for each node exactly once. Within each call to dfs()
, it performs a constant amount of work for each child. Since the sum of the sizes of all children's lists across all nodes is N - 1
(there are N - 1
edges in a tree with N
nodes), the overall time complexity is linear relative to the number of nodes in the tree.
Space Complexity:
The space complexity of the code can be analyzed in two parts: the space required for the recursion call stack and the space required for the dfs()
function execution.
-
The worst-case space complexity for the recursion call stack is
O(H)
, whereH
is the height of the tree. In the worst case, the tree can be skewed, resembling a linked list, thus the height can becomeN
, leading to a worst-case space complexity ofO(N)
. -
The additional space used by the
dfs()
function is constant, as it only uses a few integer variables (m1
,m2
, andt
).
Considering both parts, the total space complexity is O(H)
, which is O(N)
in the worst case (when the tree is a linear chain), but can be better (such as O(log N)
) if the tree is balanced.
Learn more about how to find time and space complexity quickly using problem constraints.
Which technique can we use to find the middle of a linked list?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!