Sunday, November 1, 2015

Zenefits: Validate a Directed Graph Tree

Validate if a directed graph is a valid tree.

Understand the problem:If the graph is undirected graph, it would be the same as the Leetcode question : Graph Valid Tree.

The corner case which need to be very careful is if the graph contains more than one connected components, i.e. multiple islands. In this case, the graph is not a valid tree because a tree can have one and only one root. 

The same role applies to the directed graph. For a directed graph, we can do a topological sorting. If a valid topological sorting exists, it means the graph does not contain a circle. 
But how to deal with multiple connected components? 

One solution is to calculate the in-degree for each node. For a valid tree, there should be one and only one node with in-degree 0. If not, e.g. there are two nodes with in-degree 0, the graph must not be a valid tree. Then we can also do a topological sort from this root node, avoiding starting from each and every node. 

Code (Java):
import java.util.*;

public class Solution {
    public static boolean validTree(int n, int[][] edges) {
        if (n <= 0 || edges == null || edges.length == 0) {
            return false;
        // Step 1: calculate the in-degree for each vertex, to find out the root of the tree
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (int[] edge: edges) {
            if (!inDegree.containsKey(edge[1])) {
                inDegree.put(edge[1], 1);
            } else {
                int val = inDegree.get(edge[1]);
                inDegree.put(edge[1], val + 1);
        // Iterate the inDegree and check 0 degree vertex
        int root = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!inDegree.containsKey(i)) {
                root = i;
        if (count != 1) {
            return false;
        // Step 2: transform the edge list to the adjlist
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : edges) {
            if (adjList.containsKey(edge[0])) {
                List<Integer> neighbors = adjList.get(edge[0]);
            } else {
                List<Integer> neighbors = new ArrayList<>();
                adjList.put(edge[0], neighbors);
        boolean[] visited = new boolean[n];
        return validTreeHelper(root, visited, adjList);
    private static boolean validTreeHelper(int vertexId, boolean[] visited, 
        Map<Integer, List<Integer>> adjList) {
        if (visited[vertexId]) {
            return false;
        visited[vertexId] = true;
        List<Integer> neighbors = adjList.get(vertexId);
        if (neighbors != null) {
            for (int neighbor : neighbors) {
                if (!validTreeHelper(neighbor, visited, adjList)) {
                    return false;
        visited[vertexId] = false;
        return true;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(;
        int numVertices = scanner.nextInt();
        int numEdges = scanner.nextInt();
        int[][] edges = new int[numEdges][2];
        for (int i = 0; i < numEdges; i++) {
            edges[i][0] = scanner.nextInt();
            edges[i][1] = scanner.nextInt();
        boolean result = Solution.validTree(numVertices, edges);

1 comment:

  1. To handle the case of multiple connected components, you can check if every element the array visited[] are marked to 1. Basically, all node should be reachable via root.