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.
private void Dfs(int node, bool[] visited, int[][] children) {
if (visited[node]) return;
visited[node] = true;
if (children[0][node] != -1) Dfs(children[0][node], visited, children);
if (children[1][node] != -1) Dfs(children[1][node], visited, children);
}
public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
int[] inDegree = new int[n];
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1) inDegree[leftChild[i]]++;
if (rightChild[i] != -1) 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;
bool[] visited = new bool[n];
Dfs(root, visited, new int[][] { leftChild, rightChild });
foreach (bool v in visited) {
if (!v) return false;
}
return true;
}
}The C# approach determines the root node based on the inDegree, working under the trademark binary tree outline that each node may only have a single incoming edge (or reference) unless it is the root. Exploiting this relation, all nodes should receive connectivity verification through Dfs, making sure the graph satisfies full extent reachability in step-results.