Prerequisites :- Indegree/Outdegree in Trees
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, along with a node v, count the number of neighbors of the node v.
Solution Approach:
The solution uses a straightforward approach to count the number of neighbors for the specified node in the given tree. While taking tree inputs, mark the indegree of each node, in an array called indegree and later get the indegree of node v, which shall be the no. of its neighbors.
Note: Outdegree of a node is total number of leaving vertices.Similarly, Indegree of a node is total number of entering vertices. Both of them are the same in case of undirected trees.
Time Complexity: O(E) = O(N), where N is the number of nodes and E = N - 1 is the no. of edges in the tree. The algorithm iterates through all edges once to populate the degree array.
Space Complexity: O(N), as the degree array stores information for each node.