Sponsored
Sponsored
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.
1var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
2 const parent = Array.from({ length: n }, (_, index) => index);
3 const find = (x) => {
4 if (parent[x] !== x) {
5 parent[x] = find(parent[x]);
6 }
7 return parent[x];
8 };
9
10 const union = (x, y) => {
11 const rootX = find(x);
12 const rootY = find(y);
13 if (rootX === rootY) return false;
14 parent[rootY] = rootX;
15 return true;
16 };
17
18 const hasParent = new Array(n).fill(0);
19
20 for (let i = 0; i < n; ++i) {
21 if (leftChild[i] !== -1) {
22 if (hasParent[leftChild[i]] === 1 || !union(i, leftChild[i])) {
23 return false;
24 }
25 hasParent[leftChild[i]] = 1;
26 }
27 if (rightChild[i] !== -1) {
28 if (hasParent[rightChild[i]] === 1 || !union(i, rightChild[i])) {
29 return false;
30 }
31 hasParent[rightChild[i]] = 1;
32 }
33 }
34
35 return hasParent.filter(parent => parent === 0).length === 1;
36};The JavaScript variation employs similar structures to monitor the tree integrity. Using find and union functions, this approach enforces the hierarchical conditions of nodes along with a snapshot of their root relations. In JavaScript, this procedural logic ensures the union-find checks can prevent improper cycles or multiple root scenarios.
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.
void dfs(int node, std::vector<bool>& visited, std::vector<std::vector<int>>& adj) {
if (visited[node]) return;
visited[node] = true;
for (int child : adj[node]) {
dfs(child, visited, adj);
}
}
bool validateBinaryTreeNodes(int n, std::vector<int>& leftChild, std::vector<int>& rightChild) {
std::vector<int> inDegree(n, 0);
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
if (leftChild[i] != -1) {
adj[i].push_back(leftChild[i]);
inDegree[leftChild[i]]++;
}
if (rightChild[i] != -1) {
adj[i].push_back(rightChild[i]);
inDegree[rightChild[i]]++;
}
}
int root = -1;
for (int i = 0; i < n; ++i) {
if (inDegree[i] == 0) {
if (root == -1) {
root = i;
} else {
return false;
}
}
}
if (root == -1) return false;
std::vector<bool> visited(n, false);
dfs(root, visited, adj);
for (auto v : visited) {
if (!v) return false;
}
return true;
}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.