Find Center of Star Graph

Find Center of Star Graph

What is this problem about?

The Find Center of Star Graph interview question introduces a specific type of graph called a "star graph." In a star graph with $n$ nodes, there is exactly one central node that is connected to all other $n-1$ nodes. All other nodes have a degree of 1. You are given a list of edges, where each edge is a pair of nodes. You need to find the label of the center node.

Why is this asked in interviews?

This "Easy" problem is used by companies like Microsoft and Google to test a candidate's ability to identify structural properties and optimize beyond the obvious. While you could count the degrees of all nodes ($O(N)$), the "star" property allows for an $O(1)$ solution. It evaluation whether you can notice that the center node must appear in every single edge, meaning you only need to look at any two edges to find the common node.

Algorithmic pattern used

This problem uses Graph Property Observation. Because the center node is connected to every other node, it must be present in every edge list.

1. Take the first edge: [u1, v1].
2. Take the second edge: [u2, v2].
3. The node that appears in both edges is the center.
   • If u1 == u2 or u1 == v2, then u1 is the center.
   • Otherwise, v1 must be the center.

Example explanation

Edges: [[1, 2], [5, 1], [1, 3], [1, 4]].

1. Edge 1: [1, 2].
2. Edge 2: [5, 1].
3. Check common nodes: 1 is in both edges. Result: 1.

Common mistakes candidates make

• Iterating through all edges: Building a full adjacency list or counting degrees for all edges, which takes $O(N)$ time and space.
• Overcomplicating the search: Using BFS or DFS to find the node with the highest connectivity.
• Complexity confusion: Not realizing that in a valid star graph, the first two edges are sufficient to determine the answer.

Interview preparation tip

Always look for "structural guarantees" in graph problems. Terms like "star graph," "tree," or "DAG" imply specific properties that often allow you to skip standard traversals in favor of constant-time logic.