Valid Tree - JS Solution

JS
Editorial

Approach

  • We are given an undirected graph with n nodes and an edges list. The goal is to determine whether these edges form a valid tree, assuming that no duplicate edges appear in the edges list.
  • Intuition:
    Before anything else, we check whether the graph has exactly n βˆ’ 1 edges. A tree with n nodes must have exactly n βˆ’ 1 edges, so if this fails we can return immediately.

    Once this check passes, we only need to ensure that none of the provided edges connect two nodes that are already connected through some existing path. To reason about this, imagine that every time we connect two nodes, we are gradually forming new connected structures or expanding the existing ones. Each such connected structure has its own current root that all nodes in that structure ultimately originate from.

    When we process a new edge [u, v], we look at the current roots of u and v:
    • If their roots are different, they are not yet connected, so adding the edge is safe.
    • If their roots are the same, then a path between them already exists, and adding this edge would create a cycle.
    Because the edge-count check has already guaranteed that exactly n βˆ’ 1 edges are present, if none of these edges forms a cycle, the graph must also be connected β€” and therefore it is a valid tree.
  • Quick Pre-check:
    A valid tree with n nodes must have exactly n - 1 edges. If this condition fails (edges.length !== n - 1), we immediately return false.
  • Disjoint-Set (Union–Find) Structure:
    We represent connectivity using two arrays:
    • parent[i] β€” stores the parent reference of node i in the disjoint-set forest. Initially, parent[i] = i for every node i (each node starts as its own singleton set).
    • rank[i] β€” used as a union-by-rank heuristic. For a root node i, rank[i] represents an upper bound on the number of parent[] links one might follow to reach node i from any node in its set. Since each node begins as a single-node set and so already refers to its own root, all ranks are initialized to 0. It is meaningful only for root nodes; for non-root nodes, it may be outdated and is not used.

    Why use rank and path compression? Rank makes sure trees grow minimally by always attaching the shallower tree under the deeper one, while path compression flattens existing paths during find() calls. Used together, they keep the forest almost flat at all times, ensuring each find() operation is performed in amortized near-constant time.
  • Find(x) β€” Two-Pass Path Compression:
    • Pass 1 – Root Discovery: Follow parent[] references starting from node x until reaching the root r, where parent[r] === r.
    • Pass 2 – Path Compression: Walk back from node x toward root r, updating each intermediate node’s parent[] entry to point directly to the root r.
    • Effect: This flattens the disjoint-set forest, so future find() operations on these nodes run in near-constant time.
  • Union(x, y) β€” Merge by Rank:
    • We first find the roots of nodes x and y using find(), storing them as rootX and rootY. Each represents the representative node (root) of its disjoint set.
    • If both rootX and rootY are the same, the two nodes already belong to the same component. Adding this edge would create a cycle, so we return false immediately.
    • Otherwise, we apply Union by Rank in the following order:
      • πŸ”„ Case 1 β€” rank[rootX] > rank[rootY]:
        rootX has a higher rank than rootY, so rootX becomes the parent and absorbs rootY’s set. The rank of rootX remains unchanged after the merge. Adding rootY under rootX introduces exactly one additional parent link for the nodes previously rooted at rootY to reach their new root (rootX), but does not go beyond the maximum number of parent links needed to reach rootX within its own set.
      • πŸ”„ Case 2 β€” rank[rootX] < rank[rootY]:
        rootY has a higher rank than rootX, so rootY becomes the parent and absorbs rootX’s set. The rank of rootY remains unchanged after the merge. Adding rootX under rootY introduces exactly one additional parent link for the nodes previously rooted at rootX to reach their new root (rootY), but does not go beyond the maximum number of parent links needed to reach rootY within its own set.
      • πŸ”„ Case 3 β€” rank[rootX] === rank[rootY]:
        Both roots have equal rank, so we choose rootX as the new root and increment its rank by 1. Since both sets have the same maximum number of parent links to their roots, attaching rootY under rootX makes each node in rootY’s set gain exactly one additional parent link to reach their new root. This makes the merged set’s maximum link depth one more than the maximum link depth of the individual sets before merging (considering their existing roots before the merge), which is why rank[rootX] is incremented.
  • Edge Traversal and Union:
    We iterate through each edge [u, v] in edges and call union(u, v) to connect their components if they belong to different roots. If union(u, v) ever returns false, it means the two nodes are already in the same component β€” revealing that this edge creates a cycle in the original tree, so we return false immediately.
    If all edges are processed successfully (also considering that the total edge count equals n βˆ’ 1 from the earlier pre-check), the graph is connected and acyclic, so it forms a valid tree and we return true.

Time Complexity

If the number of edges is not equal to n βˆ’ 1, we return immediately after the pre-check, since the graph cannot form a valid tree in that case. Therefore, we can assume the number of edges to be n βˆ’ 1 for the worst-case analysis.

For each edge [x, y] in edges, we call union(x, y) to merge the components containing node x and node y.

Each union(x, y) internally performs up to two find() calls (one for each node), and each find() runs in amortized O(Ξ±(n)) time due to the combined effect of path compression and union by rank. The remaining logic inside union() runs in O(1) time.

Therefore, processing all n βˆ’ 1 edges takes O((n βˆ’ 1) Β· Ξ±(n)), which is asymptotically O(n Β· Ξ±(n)) overall, where Ξ±(n) (the inverse Ackermann function) grows so slowly that it is effectively constant for all practical input sizes.

Space Complexity

The algorithm uses two auxiliary arrays β€” parent[] and rank[] β€” each of size n. Apart from these, only a few constant-size variables are used. Therefore, the total space complexity is O(n).