To solve this problem using the Disjoint Set Union (DSU) approach, we aim to union nodes based on their parent-child relationships. A valid tree should follow these rules:
Time Complexity: O(n), where n is the number of nodes, due to each union and find operation being nearly constant with path compression.
Space Complexity: O(n) for the parent array.
1#include <stdbool.h>
2
3int find(int* parent, int x) {
4 if (parent[x] != x) {
5 parent[x] = find(parent, parent[x]); // Path compression
6 }
7 return parent[x];
8}
9
10bool unionFind(int* parent, int x, int y) {
11 int rootX = find(parent, x);
12 int rootY = find(parent, y);
13
14 if (rootX == rootY) return false; // Cycle detected
15 parent[rootY] = rootX; // Union
16 return true;
17}
18
19bool validateBinaryTreeNodes(int n, int* leftChild, int leftChildSize, int* rightChild, int rightChildSize) {
20 int parent[n];
21 for (int i = 0; i < n; ++i) {
22 parent[i] = i;
23 }
24
25 int hasParent[n];
26 for (int i = 0; i < n; ++i) {
27 hasParent[i] = 0;
28 }
29
30 for (int i = 0; i < n; ++i) {
31 if (leftChild[i] != -1) {
32 if (hasParent[leftChild[i]] || !unionFind(parent, i, leftChild[i])) {
33 return false;
34 }
35 hasParent[leftChild[i]] = 1;
36 }
37 if (rightChild[i] != -1) {
38 if (hasParent[rightChild[i]] || !unionFind(parent, i, rightChild[i])) {
39 return false;
40 }
41 hasParent[rightChild[i]] = 1;
42 }
43 }
44
45 int rootCount = 0;
46 for (int i = 0; i < n; ++i) {
47 if (!hasParent[i]) {
48 ++rootCount;
49 }
50 }
51
52 return rootCount == 1;
53}The solution creates a parent array to track the roots of each node using the find function with path compression. The unionFind function unites two components. If unionFind finds that two nodes are already connected, it indicates a cycle. The solution verifies each node only has one parent and no cycle exists by unionizing their parent-child relations. Finally, it ensures exactly one node has no parent (root node).
This approach involves calculating the in-degree of each node and checking connectivity via a DFS. The key aspects of a tree like single-root presence and cycle-checking can be managed by:
Time Complexity: O(n), since each node and its immediate edges are evaluated once in each step, including in-drives calculations and DFS.
Space Complexity: O(n) for holding visited tracking and in-degree counts.
1#include <vector>
2
3void dfs(int node, std::vector<bool>& visited, std::vector<std::vector<int>>& adj) {
4 if (visited[node]) return;
5 visited[node] = true;
6 for (int child : adj[node]) {
7 dfs(child, visited, adj);
8 }
9}
10
11bool validateBinaryTreeNodes(int n, std::vector<int>& leftChild, std::vector<int>& rightChild) {
12 std::vector<int> inDegree(n, 0);
13 std::vector<std::vector<int>> adj(n);
14
15 for (int i = 0; i < n; ++i) {
16 if (leftChild[i] != -1) {
17 adj[i].push_back(leftChild[i]);
18 inDegree[leftChild[i]]++;
19 }
20 if (rightChild[i] != -1) {
21 adj[i].push_back(rightChild[i]);
22 inDegree[rightChild[i]]++;
23 }
24 }
25
26 int root = -1;
27 for (int i = 0; i < n; ++i) {
28 if (inDegree[i] == 0) {
29 if (root == -1) {
30 root = i;
31 } else {
32 return false;
33 }
34 }
35 }
36
37 if (root == -1) return false;
38
39 std::vector<bool> visited(n, false);
40 dfs(root, visited, adj);
41
42 for (auto v : visited) {
43 if (!v) return false;
44 }
45 return true;
46}This solution represents each node and its relationships as directed graph edges, forming an adjacency list adj. It begins by resolving in-degrees to locate the root. The dfs ensures all nodes are explored from the root, confirming all nodes are part of a single, adequately connected component with single ingress from the root.