Validate Binary Tree Nodes

• Initialize a Union-Find (DSU) data structure with n components, one for each node.
• Initialize an inDegree array of size n to all zeros to track the number of parents for each node.
• Iterate through each node p from 0 to n-1.
• For each child c (leftChild[p] or rightChild[p]):
  • If c is not -1:
    • If c already has a parent (inDegree[c] == 1), it violates the binary tree property. Return false.
    • If p and c are already in the same connected component (find(p) == find(c)), adding the edge p -> c would create a cycle. Return false.
    • If the checks pass, increment inDegree[c] and perform union(p, c) to merge their sets.
• After iterating through all nodes, we must have exactly one connected component and exactly one root.
• The number of components in the DSU must be 1.
• The number of nodes with an in-degree of 0 (roots) must be 1.
• If both conditions hold, return true; otherwise, return false.

A valid binary tree must be a single connected component, contain no cycles, and every node (except the root) must have exactly one parent. This approach tackles these conditions using a combination of an in-degree count and a DSU data structure.

1. Parent Uniqueness: We use an inDegree array to track the number of parents for each node. As we process the leftChild and rightChild arrays, we check the child's in-degree. If a child node is about to be assigned a second parent, we immediately know the structure is invalid.

2. Cycle Detection & Connectivity: A DSU data structure is initialized with n nodes, each in its own set. For each parent-child relationship p -> c, we first check for parent uniqueness. Then, we check if p and c are already in the same set using the find operation. If they are, it implies that an undirected path already exists between them. Since c has no other parent, this must mean c is an ancestor of p, so adding the edge p -> c would form a cycle. If no cycle is formed, we union them, merging their sets and decrementing the component count.

3. Final Validation: After processing all edges, a valid tree must consist of a single component with a single root. We check that the final number of components in the DSU is 1 and that the number of nodes with an in-degree of 0 is also exactly 1.

1class Solution {2    class DSU {3        private int[] parent;4        private int components;5 6        public DSU(int n) {7            parent = new int[n];8            components = n;9            for (int i = 0; i < n; i++) {10                parent[i] = i;11            }12        }13 14        public int find(int i) {15            if (parent[i] == i) {16                return i;17            }18            return parent[i] = find(parent[i]);19        }20 21        public boolean union(int i, int j) {22            int rootI = find(i);23            int rootJ = find(j);24            if (rootI != rootJ) {25                parent[rootJ] = rootI;26                components--;27                return true;28            }29            return false;30        }31        32        public int getComponents() {33            return components;34        }35    }36 37    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {38        DSU dsu = new DSU(n);39        int[] inDegree = new int[n];40        41        for (int i = 0; i < n; i++) {42            int lc = leftChild[i];43            int rc = rightChild[i];44 45            if (lc != -1) {46                if (inDegree[lc] > 0) return false; // Already has a parent47                if (dsu.find(i) == dsu.find(lc)) return false; // Cycle48                dsu.union(i, lc);49                inDegree[lc]++;50            }51 52            if (rc != -1) {53                if (inDegree[rc] > 0) return false; // Already has a parent54                if (dsu.find(i) == dsu.find(rc)) return false; // Cycle55                dsu.union(i, rc);56                inDegree[rc]++;57            }58        }59 60        int rootCount = 0;61        for (int i = 0; i < n; i++) {62            if (inDegree[i] == 0) {63                rootCount++;64            }65        }66 67        return rootCount == 1 && dsu.getComponents() == 1;68    }69}

• Create an inDegree array of size n and initialize it to all zeros.
• Populate the inDegree array by iterating through leftChild and rightChild arrays. For each valid child, increment its in-degree.
• Find the root of the potential tree. Iterate through the inDegree array:
  • A node i is a potential root if inDegree[i] == 0.
  • If there is not exactly one node with an in-degree of 0, return false.
  • If any node has an in-degree greater than 1, return false.
• If a unique root is found, perform a graph traversal (BFS or DFS) starting from that root.
• Keep a count of the number of nodes visited during the traversal.
• After the traversal, if the number of visited nodes is equal to n, it means all nodes are connected in a single component. Return true.
• Otherwise, the graph is disconnected (a forest), so return false.

A valid binary tree has key properties that we can check sequentially for an elegant and efficient solution:

1. Single Parent & Single Root Rule: A binary tree must have exactly one root (a node with no parent), and every other node must have exactly one parent. We can verify this by computing the in-degree for every node. We iterate through all parent-child connections, build an inDegree array, and then scan this array. If we find any node with an in-degree greater than 1, or if we don't find exactly one node with an in-degree of 0, the structure is invalid.

2. Connectivity & Acyclicity: If the parent/root rules hold, the graph consists of one or more components, each of which is a tree. To be a single valid binary tree, all n nodes must belong to the component of the single root we identified. We can verify this by starting a traversal (BFS or DFS) from the root. By counting the nodes visited, we can determine if the graph is fully connected. If the traversal visits exactly n nodes, then all nodes are reachable from the single root, forming one connected component. This also implicitly confirms there are no cycles, as a cycle would have violated the in-degree rules.

This leads to a clean, multi-step algorithm that is easy to implement and understand.

1import java.util.Queue;2import java.util.LinkedList;3 4class Solution {5    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {6        int[] inDegree = new int[n];7        for (int i = 0; i < n; i++) {8            if (leftChild[i] != -1) {9                inDegree[leftChild[i]]++;10            }11            if (rightChild[i] != -1) {12                inDegree[rightChild[i]]++;13            }14        }15 16        int root = -1;17        for (int i = 0; i < n; i++) {18            if (inDegree[i] > 1) {19                return false; // Node with more than one parent20            }21            if (inDegree[i] == 0) {22                if (root != -1) {23                    return false; // More than one root24                }25                root = i;26            }27        }28 29        if (root == -1) {30            return false; // No root found (e.g., a cycle)31        }32 33        // BFS to check connectivity and count visited nodes34        Queue<Integer> queue = new LinkedList<>();35        boolean[] visited = new boolean[n];36        int visitedCount = 0;37 38        queue.offer(root);39        visited[root] = true;40        visitedCount++;41 42        while (!queue.isEmpty()) {43            int u = queue.poll();44 45            int lc = leftChild[u];46            if (lc != -1) {47                // This check is technically redundant if in-degree checks passed,48                // but provides extra safety.49                if (visited[lc]) return false; 50                visited[lc] = true;51                queue.offer(lc);52                visitedCount++;53            }54 55            int rc = rightChild[u];56            if (rc != -1) {57                if (visited[rc]) return false;58                visited[rc] = true;59                queue.offer(rc);60                visitedCount++;61            }62        }63 64        return visitedCount == n;65    }66}