easyTreesPattern: DFS
Count Tree Nodes Solution
Problem Statement
Given the root of a tree represented by an adjacency list, return the total number of nodes in the tree. The tree is guaranteed to be connected and acyclic.
Examples
Example 1:
Input:{"n":5,"edges":[[0,1],[0,2],[1,3],[1,4]]}
Output:5
Explanation: The tree has 5 nodes, labeled 0 through 4. The edges define the connections: 0 is connected to 1 and 2. Node 1 is connected to 0, 3, and 4. Nodes 2, 3, and 4 are leaf nodes. The total count is 5.
Example 2:
Input:{"n":1,"edges":[]}
Output:1
Explanation: A tree with only one node (the root) has a total count of 1 node.
Example 3:
Input:{"n":3,"edges":[[0,1],[1,2]]}
Output:3
Explanation: The tree has 3 nodes. The structure is a line: 0-1-2. The total count is 3.
Constraints
- 1 <= n <= 1000, where n is the number of nodes.
- The tree is connected and acyclic.
- The nodes are labeled from 0 to n-1.
- edges.length == n - 1, if n > 1.
- edges[i].length == 2
Time: O(1) Space: O(1)
The problem states that 'n' represents the total number of nodes in the tree. Since the input guarantees a connected tree, the total number of nodes is simply 'n'. No traversal or graph construction is necessary.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def count_nodes(n: int, edges: list[list[int]]) -> int:
return n