Problem Description

The "Validate Binary Tree Nodes" problem asks you to determine if a set of nodes and their left and right child relationships form exactly one valid binary tree.

• You are given an integer n representing the number of nodes, labeled from 0 to n-1.
• Two integer arrays, leftChild and rightChild, each of length n, where leftChild[i] and rightChild[i] are the left and right child of node i. If a child does not exist, it is -1.

You must determine if all nodes together form exactly one valid binary tree. The key constraints are:

• There is exactly one root node (a node with no parent).
• Each node (except the root) has exactly one parent.
• There are no cycles (the structure is acyclic).
• All n nodes are connected (no isolated nodes or separate trees).

Thought Process

To validate a binary tree, we need to check for three main properties:

• Single Root: Only one node should have no parent.
• No Multiple Parents: Each node (except the root) must have exactly one parent.
• No Cycles and Full Connectivity: All nodes must be reachable from the root, and no cycles should exist.

The brute-force way would be to try to reconstruct the tree and check all these properties separately, but this is inefficient. Instead, we can optimize by:

• Using an array to count parent references for each node.
• Identifying the root as the node with zero parents.
• Using Depth-First Search (DFS) or Breadth-First Search (BFS) from the root to check for cycles and full connectivity.

The main trick is to combine these checks efficiently, ensuring we visit each node only once.

Solution Approach

Here’s a step-by-step approach to solve the problem:

1. Count Parent References:
   • Initialize a parent array of size n with all entries set to -1.
   • For each node, if it has a left or right child, set parent[child] to the current node.
   • If a child already has a parent, it means the node has multiple parents, which is invalid.
2. Identify the Root:
   • After processing, count how many nodes have parent[i] == -1. There must be exactly one such node (the root).
3. Check for Cycles and Connectivity:
   • From the root, perform DFS (or BFS) traversal, marking nodes as visited.
   • If a node is visited twice, there is a cycle.
   • If after traversal not all nodes are visited, the graph is disconnected.
4. Return the Result:
   • If all checks pass, return True; otherwise, return False.

This approach ensures all binary tree properties are validated efficiently.

Example Walkthrough

Example:
n = 4, leftChild = [1, -1, 3, -1], rightChild = [2, -1, -1, -1]

1. Parent Array:
   • Start with parent = [-1, -1, -1, -1].
   • Node 0: leftChild=1, rightChild=2 → parent[1]=0, parent[2]=0.
   • Node 2: leftChild=3 → parent[3]=2.
   • Result: parent = [-1, 0, 0, 2]
2. Find Root:
   • Only node 0 has parent[0] == -1, so root = 0.
3. DFS Traversal:
   • Start at root (0): visit 0, then 1 and 2.
   • From 2: visit 3.
   • Visited nodes: {0, 1, 2, 3} (all nodes).
4. Validation:
   • No cycles, one root, all nodes connected → Valid.

Time and Space Complexity

• Brute-force:
  • Checking all possible parent-child combinations is O(n^2).
• Optimized Approach:
  • Time Complexity: O(n), since we traverse each node and edge once.
  • Space Complexity: O(n), for the parent and visited arrays.

This efficiency comes from processing each node and relationship in a single pass.

Summary

To validate binary tree nodes, we ensure there is a single root, no node has multiple parents, no cycles exist, and all nodes are connected. By tracking parent relationships and using traversal to check connectivity and cycles, we efficiently verify all conditions for a valid binary tree in linear time.

Code Implementation

class Solution:
    def validateBinaryTreeNodes(self, n, leftChild, rightChild):
        parent = [-1] * n
        for i in range(n):
            for child in [leftChild[i], rightChild[i]]:
                if child == -1:
                    continue
                if parent[child] != -1:
                    return False
                parent[child] = i
        roots = [i for i in range(n) if parent[i] == -1]
        if len(roots) != 1:
            return False
        root = roots[0]
        visited = set()
        def dfs(node):
            if node == -1:
                return
            if node in visited:
                return
            visited.add(node)
            dfs(leftChild[node])
            dfs(rightChild[node])
        dfs(root)
        return len(visited) == n
      

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> parent(n, -1);
        for (int i = 0; i < n; ++i) {
            for (int child : {leftChild[i], rightChild[i]}) {
                if (child == -1) continue;
                if (parent[child] != -1) return false;
                parent[child] = i;
            }
        }
        int root = -1, rootCount = 0;
        for (int i = 0; i < n; ++i) {
            if (parent[i] == -1) {
                root = i;
                rootCount++;
            }
        }
        if (rootCount != 1) return false;
        vector<bool> visited(n, false);
        function<void(int)> dfs = [&](int node) {
            if (node == -1 || visited[node]) return;
            visited[node] = true;
            dfs(leftChild[node]);
            dfs(rightChild[node]);
        };
        dfs(root);
        for (bool v : visited) if (!v) return false;
        return true;
    }
};
      

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        for (int i = 0; i < n; i++) {
            for (int child : new int[]{leftChild[i], rightChild[i]}) {
                if (child == -1) continue;
                if (parent[child] != -1) return false;
                parent[child] = i;
            }
        }
        int root = -1, rootCount = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == -1) {
                root = i;
                rootCount++;
            }
        }
        if (rootCount != 1) return false;
        boolean[] visited = new boolean[n];
        dfs(root, leftChild, rightChild, visited);
        for (boolean v : visited) if (!v) return false;
        return true;
    }
    private void dfs(int node, int[] left, int[] right, boolean[] visited) {
        if (node == -1 || visited[node]) return;
        visited[node] = true;
        dfs(left[node], left, right, visited);
        dfs(right[node], left, right, visited);
    }
}
      

var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
    let parent = Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        for (const child of [leftChild[i], rightChild[i]]) {
            if (child === -1) continue;
            if (parent[child] !== -1) return false;
            parent[child] = i;
        }
    }
    let roots = [];
    for (let i = 0; i < n; i++) {
        if (parent[i] === -1) roots.push(i);
    }
    if (roots.length !== 1) return false;
    let visited = new Set();
    function dfs(node) {
        if (node === -1 || visited.has(node)) return;
        visited.add(node);
        dfs(leftChild[node]);
        dfs(rightChild[node]);
    }
    dfs(roots[0]);
    return visited.size === n;
};