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.
1class Solution {
2 public int find(int[] parent, int x) {
3 if (parent[x] != x) {
4 parent[x] = find(parent, parent[x]);
5 }
6 return parent[x];
7 }
8
9 public boolean unionFind(int[] parent, int x, int y) {
10 int rootX = find(parent, x);
11 int rootY = find(parent, y);
12
13 if (rootX == rootY) return false;
14 parent[rootY] = rootX;
15 return true;
16 }
17
18 public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
19 int[] parent = new int[n];
20 int[] hasParent = new int[n];
21 for (int i = 0; i < n; ++i) {
22 parent[i] = i;
23 }
24
25 for (int i = 0; i < n; ++i) {
26 if (leftChild[i] != -1) {
27 if (hasParent[leftChild[i]] == 1 || !unionFind(parent, i, leftChild[i])) {
28 return false;
29 }
30 hasParent[leftChild[i]] = 1;
31 }
32 if (rightChild[i] != -1) {
33 if (hasParent[rightChild[i]] == 1 || !unionFind(parent, i, rightChild[i])) {
34 return false;
35 }
36 hasParent[rightChild[i]] = 1;
37 }
38 }
39
40 int rootCount = 0;
41 for (int i = 0; i < n; ++i) {
42 if (hasParent[i] == 0) {
43 rootCount++;
44 }
45 }
46
47 return rootCount == 1;
48 }
49}This Java solution, similar in logic to the C and C++ solutions, uses a union-find structure managed through unionFind and find methods. The hasParent array manages in-degree checks to ensure a single parent per node, avoiding tree invalidation by multiple roots or cycles. After scanning nodes, it confirms just one root using hasParent.
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 <stdbool.h>
2#include <string.h>
3
4void dfs(int node, int* visited, int** children, int n) {
5 if (visited[node]) return;
6 visited[node] = 1;
7 if (children[0][node] != -1) dfs(children[0][node], visited, children, n);
8 if (children[1][node] != -1) dfs(children[1][node], visited, children, n);
9}
10
11bool validateBinaryTreeNodes(int n, int* leftChild, int leftChildSize, int* rightChild, int rightChildSize) {
12 int inDegree[n];
13 memset(inDegree, 0, sizeof(inDegree));
14
15 for (int i = 0; i < n; ++i) {
16 if (leftChild[i] != -1) ++inDegree[leftChild[i]];
17 if (rightChild[i] != -1) ++inDegree[rightChild[i]];
18 }
19
20 int root = -1;
21 for (int i = 0; i < n; ++i) {
22 if (inDegree[i] == 0) {
23 if (root == -1) {
24 root = i;
25 } else {
26 return false; // more than one root
27 }
28 }
29 }
30
31 if (root == -1) return false; // no root
32
33 int visited[n];
34 memset(visited, 0, sizeof(visited));
35 dfs(root, visited, (int*[]){leftChild, rightChild}, n);
36
37 for (int i = 0; i < n; ++i) {
38 if (!visited[i]) return false; // not fully connected
39 }
40
41 return true;
42}In this C solution, the algorithm starts by calculating the in-degree for each node, which should equal zero for the root node. A DFS checks connectivity from a root node, ensuring all nodes are part of one connected graph and are reachable. Each node is visited once, ensuring an entire traversal defines the single connected component rule of trees.