1719. Number Of Ways To Reconstruct A Tree LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1719. Number Of Ways To Reconstruct A Tree LeetCode Solution with the best time and space complexity. The solution to Number Of Ways To Reconstruct A Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Number Of Ways To Reconstruct A Tree solution in C++
  4. Number Of Ways To Reconstruct A Tree solution in Java
  5. Number Of Ways To Reconstruct A Tree solution in Python
  6. Additional Resources
1719. Number Of Ways To Reconstruct A Tree LeetCode Solution image

Problem Statement of Number Of Ways To Reconstruct A Tree

You are given an array pairs, where pairs[i] = [xi, yi], and:

There are no duplicates.
xi 1

A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.
An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.

Example 1:

Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.

Example 2:

Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3:

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.

Constraints:

1 <= pairs.length <= 105
1 <= xi < yi <= 500
The elements in pairs are unique.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(500 + n) = O(n)

1719. Number Of Ways To Reconstruct A Tree LeetCode Solution in C++

class Solution {
 public:
  int checkWays(vector<vector<int>>& pairs) {
    constexpr int kMax = 501;
    unordered_map<int, vector<int>> graph;
    vector<int> degrees(kMax);
    vector<vector<bool>> connected(kMax, vector<bool>(kMax));

    for (const vector<int>& pair : pairs) {
      const int u = pair[0];
      const int v = pair[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
      ++degrees[u];
      ++degrees[v];
      connected[u][v] = true;
      connected[v][u] = true;
    }

    // For each node, sort its children by degrees in descending order.
    for (auto& [_, children] : graph)
      ranges::sort(children, ranges::greater{},
                   [&degrees](int child) { return degrees[child]; });

    const int root = getRoot(degrees, graph.size());
    if (root == -1)
      return 0;
    if (!dfs(graph, root, degrees, connected, {}, vector<bool>(kMax)))
      return 0;
    return hasMoreThanOneWay ? 2 : 1;
  }

 private:
  bool hasMoreThanOneWay = false;

  // Returns the root by finding the node with a degree that equals to n - 1.
  int getRoot(const vector<int>& degrees, int n) {
    for (int i = 1; i < degrees.size(); ++i)
      if (degrees[i] == n - 1)
        return i;
    return -1;
  }

  // Returns true if each node rooted at u is connected to all of its ancestors.
  bool dfs(const unordered_map<int, vector<int>>& graph, int u,
           vector<int>& degrees, vector<vector<bool>>& connected,
           vector<int>&& ancestors, vector<bool>&& seen) {
    seen[u] = true;

    for (const int ancestor : ancestors)
      if (!connected[u][ancestor])
        return false;

    ancestors.push_back(u);

    for (const int v : graph.at(u)) {
      if (seen[v])
        continue;
      // We can swap u with v, so there are more than one way.
      if (degrees[v] == degrees[u])
        hasMoreThanOneWay = true;
      if (!dfs(graph, v, degrees, connected, std::move(ancestors),
               std::move(seen)))
        return false;
    }

    ancestors.pop_back();
    return true;
  }
};
/* code provided by PROGIEZ */

1719. Number Of Ways To Reconstruct A Tree LeetCode Solution in Java

class Solution {
  public int checkWays(int[][] pairs) {
    final int kMax = 501;
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] degrees = new int[kMax];
    boolean[][] connected = new boolean[kMax][kMax];

    for (int[] pair : pairs) {
      final int u = pair[0];
      final int v = pair[1];
      graph.putIfAbsent(u, new ArrayList<>());
      graph.putIfAbsent(v, new ArrayList<>());
      graph.get(u).add(v);
      graph.get(v).add(u);
      ++degrees[u];
      ++degrees[v];
      connected[u][v] = true;
      connected[v][u] = true;
    }

    // For each node, sort its children by degrees in descending order.
    for (final int u : graph.keySet())
      graph.get(u).sort((a, b) -> Integer.compare(degrees[b], degrees[a]));

    final int root = getRoot(degrees, graph.keySet().size());
    if (root == -1)
      return 0;
    if (!dfs(graph, root, degrees, connected, new ArrayList<>(), new boolean[kMax]))
      return 0;
    return hasMoreThanOneWay ? 2 : 1;
  }

  private boolean hasMoreThanOneWay = false;

  // Returns the root by finding the node with a degree that equals to n - 1.
  private int getRoot(int[] degrees, int n) {
    for (int i = 1; i < degrees.length; ++i)
      if (degrees[i] == n - 1)
        return i;
    return -1;
  }

  // Returns true if each node rooted at u is connected to all of its ancestors.
  private boolean dfs(Map<Integer, List<Integer>> graph, int u, int[] degrees,
                      boolean[][] connected, List<Integer> ancestors, boolean[] seen) {
    seen[u] = true;

    for (final int ancestor : ancestors)
      if (!connected[u][ancestor])
        return false;

    ancestors.add(u);

    for (final int v : graph.get(u)) {
      if (seen[v])
        continue;
      // We can swap u with v, so there are more than one way.
      if (degrees[v] == degrees[u])
        hasMoreThanOneWay = true;
      if (!dfs(graph, v, degrees, connected, ancestors, seen))
        return false;
    }

    ancestors.remove(ancestors.size() - 1);
    return true;
  }
}
// code provided by PROGIEZ

1719. Number Of Ways To Reconstruct A Tree LeetCode Solution in Python

class Solution:
  def checkWays(self, pairs: list[list[int]]) -> int:
    kMax = 501
    graph = collections.defaultdict(list)
    degrees = [0] * kMax
    connected = [[False] * kMax for _ in range(kMax)]

    for u, v in pairs:
      graph[u].append(v)
      graph[v].append(u)
      degrees[u] += 1
      degrees[v] += 1
      connected[u][v] = True
      connected[v][u] = True

    # For each node, sort its children by degrees in descending order.
    for _, children in graph.items():
      children.sort(key=lambda x: -degrees[x])

    # Find the root with a degree that equals to n - 1.
    root = next((i for i, d in enumerate(degrees) if d == len(graph) - 1), -1)
    if root == -1:
      return 0

    hasMoreThanOneWay = False

    def dfs(u: int, ancestors: list[int], seen: list[bool]) -> bool:
      """
      Returns True if each node rooted at u is connected to all of its
      ancestors.
      """
      nonlocal hasMoreThanOneWay
      seen[u] = True
      for ancestor in ancestors:
        if not connected[u][ancestor]:
          return False
      ancestors.append(u)
      for v in graph[u]:
        if seen[v]:
          continue
        if degrees[v] == degrees[u]:
          hasMoreThanOneWay = True
        if not dfs(v, ancestors, seen):
          return False
      ancestors.pop()
      return True

    if not dfs(root, [], [False] * kMax):
      return 0
    return 2 if hasMoreThanOneWay else 1
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.