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 <vector>
2#include <unordered_set>
3
4class DSU {
5 std::vector<int> parent;
6public:
7 DSU(int n) {
8 parent.resize(n);
9 for (int i = 0; i < n; ++i) parent[i] = i;
10 }
11
12 int find(int x) {
13 if (parent[x] != x)
14 parent[x] = find(parent[x]);
15 return parent[x];
16 }
17
18 bool unionSets(int x, int y) {
19 int rootX = find(x), rootY = find(y);
20 if (rootX == rootY) return false;
21 parent[rootY] = rootX;
22 return true;
23 }
24};
25
26bool validateBinaryTreeNodes(int n, std::vector<int>& leftChild, std::vector<int>& rightChild) {
27 DSU dsu(n);
28 std::vector<int> inDegree(n, 0);
29
30 for (int i = 0; i < n; ++i) {
31 if (leftChild[i] != -1) {
32 if (++inDegree[leftChild[i]] > 1 || !dsu.unionSets(i, leftChild[i]))
33 return false;
34 }
35 if (rightChild[i] != -1) {
36 if (++inDegree[rightChild[i]] > 1 || !dsu.unionSets(i, rightChild[i]))
37 return false;
38 }
39 }
40
41 int rootCount = 0;
42 for (int i = 0; i < n; ++i) {
43 if (dsu.find(i) == i) ++rootCount;
44 }
45
46 return rootCount == 1;
47}This C++ solution is a close variant of the C example. It uses a class DSU structuring the union-find operations. The solution primarily checks for:
Vector inDegree tracks in-degrees, and the DSU tracks roots. After processing all nodes, the algorithm checks the single connected component from the root count.
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.
1var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
2 const inDegree = new Array(n).fill(0);
3
4 for (let i = 0; i < n; i++) {
5 if (leftChild[i] !== -1) inDegree[leftChild[i]]++;
6 if (rightChild[i] !== -1) inDegree[rightChild[i]]++;
7 }
8
9 let root = -1;
10 for (let i = 0; i < n; i++) {
11 if (inDegree[i] === 0) {
12 if (root === -1) {
13 root = i;
14 } else {
15 return false; // more than one root
16 }
17 }
18 }
19
20 if (root === -1) return false; // no root
21
22 const visited = new Array(n).fill(false);
23
24 const dfs = (node) => {
25 if (visited[node]) return;
26 visited[node] = true;
27
28 if (leftChild[node] !== -1) dfs(leftChild[node]);
29 if (rightChild[node] !== -1) dfs(rightChild[node]);
30 };
31
32 dfs(root);
33
34 return visited.every(v => v);
35};This JavaScript implementation similarly follows through verifying in-degree checks to locate the root and establishes a connection by guaranteeing complete DFS exploration from the root. This substantiates consistency in forming the tree in which connectivity is thoroughly enforced, extending checks across all nodes considered without overridden exceptions.