Validate Binary Tree Nodes - Leetcode Solution

Problem Statement: You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

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

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

Approach: To form a valid binary tree, we need to ensure that each node in the tree has at most 2 children and that there are no cycles. We can use depth-first search to traverse the tree and keep track of visited nodes and detect cycles.

We start by marking all the nodes as unvisited and iterate through all the nodes. For each unvisited node, we perform a DFS and mark all of its child nodes as visited. If we encounter a visited node during DFS, it means that there is a cycle in the graph and the tree is not valid.

After visiting all the nodes, we check if the number of visited nodes is equal to n, the total number of nodes. If the two values are equal, it means that all nodes are connected and form a valid binary tree. Otherwise, the tree is not valid.

Solution:

class Solution { public: bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) { vector<bool> visited(n, false); vector<vector<int>> graph(n);

    // build the graph
    for(int i=0; i<n; i++) {
        if(leftChild[i] != -1) graph[i].push_back(leftChild[i]);
        if(rightChild[i] != -1) graph[i].push_back(rightChild[i]);
    }
    
    // perform DFS on each unvisited node
    for(int i=0; i<n; i++) {
        if(!visited[i]) {
            if(dfs(i, -1, graph, visited)) return false;
        }
    }
    
    // count the number of visited nodes
    int count = 0;
    for(int i=0; i<n; i++) {
        if(visited[i]) count++;
    }
    
    return count == n;
}

bool dfs(int node, int parent, vector<vector<int>>& graph, vector<bool>& visited) {
    // mark the current node as visited
    visited[node] = true;
    
    for(int j=0; j<graph[node].size(); j++) {
        int neighbor = graph[node][j];
        // if neighbor is parent, continue
        if(neighbor == parent) continue;
        // if neighbor is visited or
        // neighbor is not visited and there is a cycle in its subtree, return true
        if(visited[neighbor] || dfs(neighbor, node, graph, visited)) return true;
    }
    
    return false;
}

};

Time Complexity: The time complexity of the above algorithm is O(n), where n is the number of nodes in the tree. We visit each node only once, and for each node, we perform constant-time operations to check if it has a valid child and mark it as visited.

Space Complexity: The space complexity is O(n), to store the binary tree as a graph and keep track of visited nodes.

1