Buttercola: Zenefits: Validate Graph Binary Tree

Buttercola: Zenefits: Validate Graph Binary Tree
Determine if a directed graph is a binary tree. If yes, print out the tree in string format. 

Input: (A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)
Output: (A(B(D)(G))(C(E(F))(H))))
ie.. (parent(child)(child))

If not, print out the error code Error code    Type of error
E1              More than 2 children
E2              Duplicate edges -- (A,B) (A,B)
E3              Cycle present
E4              Mulitple roots
E5              Another other error

    public String graphValidBinaryTree(char[][] edges) {

        if (edges == null || edges.length == 0) {

            return "E5";

        }

         

        // Check inDegree for each node

        Map<Character, Integer> inDegree = new HashMap<>();

        for (char[] edge : edges) {

            if (inDegree.containsKey(edge[1])) {

                int degree = inDegree.get(edge[1]);

                inDegree.put(edge[1], degree + 1);

            } else {

                inDegree.put(edge[1], 1);

            }

             

            if (!inDegree.containsKey(edge[0])) {

                inDegree.put(edge[0], 0);

            }

        }

         

        // For a valid binary tree, there is one and only one node with inDegree 0, and all the other nodes

        // has inDegree 1

        char root = '\0';

        int count = 0;

        for (char vertexId : inDegree.keySet()) {

            if (inDegree.get(vertexId) == 0) {

                root = vertexId;

                count++;

            }

            if (count > 1) {

                return "E4";

            }

             

            if (inDegree.get(vertexId) > 1) {

                return "E4";

            }

        }

         

        // No root

        if (count == 0) {

            return "E3";

        }

         

        // Step 2: transform the edge list to adjList

        Map<Character, Set<Character>> adjList = new HashMap<>();

        for (char[] edge : edges) {

            if (adjList.containsKey(edge[0])) {

                Set<Character> neighbors = adjList.get(edge[0]);

                // Duplicate edges

                if (neighbors.contains(edge[1])) {

                    return "E2";

                } else {

                    neighbors.add(edge[1]);

                }

                // More than 2 children

                if (neighbors.size() > 2) {

                    return "E1";

                }

            } else {

                Set<Character> neighbors = new HashSet<>();

                neighbors.add(edge[1]);

                adjList.put(edge[0], neighbors);

            }

        }

         

        // Step 3: do a topological sort, if not exist, return E3, cycle presents

        // Note: Couldn't use a boolean[] visited, because vertexId is char

        // Have to use a set

        Set<Character> visited = new HashSet<>();

        boolean ans = toplogicalSort(root, visited, adjList);

         

        if (!ans) {

            return "E3";

        }

         

        // Step 4: there must be valid binary tree exists, output the results.

        String result = treeToString(root, adjList);

         

        return result;

    }

     

    private boolean toplogicalSort(char vertex, Set<Character> visited, Map<Character, Set<Character>> adjList) {

        if (visited.contains(vertex)) {

            return false;

        }

         

        visited.add(vertex);

         

        Set<Character> neighbors = adjList.get(vertex);

         

        if (neighbors != null) {

            for (char neighbor : neighbors) {

                if (!toplogicalSort(neighbor, visited, adjList)) {

                    return false;

                }

            }

        }

         

        visited.remove(vertex);

         

        return true;

    }

     

    private String treeToString(char root, Map<Character, Set<Character>> adjList) {

        Set<Character> neighbors = adjList.get(root);

         

        if (neighbors == null || neighbors.size() == 0) {

            return "(" + root + ")";

        }

         

        StringBuffer result = new StringBuffer();

        result.append("(" + root);

         

        for (char neighbor : neighbors) {

            result.append(treeToString(neighbor, adjList));

        }

         

        result.append(")");

         

        return result.toString();

         

    }

     

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

         

        int numEdges = sc.nextInt();

        char[][] edges = new char[numEdges][2];

         

        for (int i = 0; i < numEdges; i++) {

            String edge = sc.next();

            edges[i][0] = edge.charAt(1);

            edges[i][1] = edge.charAt(3);

        }

         

        Solution solution = new Solution();

        String result = solution.graphValidBinaryTree(edges);

         

        System.out.println(result);

         

        sc.close();

    }

http://yuanhsh.iteye.com/blog/2207890

1. public class GraphEdgeTree {  
2.   
3.     public static class Edge {  
4.         char from, to;  
5.         public Edge(String exp) {  
6.             String[] nodes = exp.replaceAll("[\\(\\)\\s]", "").split(",");  
7.             from = nodes[0].charAt(0);  
8.             to = nodes[1].charAt(0);  
9.         }  
10.     }  
11.       
12.     private Map<Character, Character> map = new HashMap<>();  
13.     private Map<Character, Set<Character>> childMap = new HashMap<>();  
14.     private List<Edge> edges = new ArrayList<>();  
15.       
16.     public GraphEdgeTree(String exp) {  
17.         String[] arr = exp.split("\\s");  
18.         for(String str:arr) {  
19.             Edge edge = new Edge(str);  
20.             edges.add(edge);  
21.             map.put(edge.from, edge.from);  
22.             map.put(edge.to, edge.to);  
23.               
24.             Set<Character> children = childMap.get(edge.from);  
25.             if(children == null) {  
26.                 children = new HashSet<Character>();  
27.             }  
28.             children.add(edge.to);  
29.             childMap.put(edge.from, children);  
30.         }  
31.     }  
32.       
33.     public Character find(char x) {  
34.         Character parent = map.get(x);  
35.         if(parent == null || parent == x) {  
36.             return parent;  
37.         }  
38.         return find(parent);  
39.     }  
40.       
41.     public void union(char x, char y) {  
42.         Character xp = find(x);  
43.         Character yp = find(y);  
44.         map.put(xp, yp);  
45.     }  
46.       
47.     public boolean isEdgeExisted(Edge edge) {  
48.         Character p = map.get(edge.to);  
49.         return p != null && p == edge.from;  
50.     }  
51.       
52.     public String buildTree() {  
53.         for(Character key:childMap.keySet()) {  
54.             Set<Character> set = childMap.get(key);  
55.             if(set != null && set.size()>2) {  
56.                 return "E1";  
57.             }  
58.         }  
59.         for(Edge edge:edges) {  
60.             if(isEdgeExisted(edge)) {  
61.                 return "E2";  
62.             }  
63.             char xp = find(edge.from);  
64.             char yp = find(edge.to);  
65.             if(xp == yp) {  
66.                 return "E3";  
67.             }  
68.             union(edge.to, edge.from);  
69.         }  
70.         if(rootNum() > 1) {  
71.             return "E4";  
72.         }  
73.         return null;  
74.     }  
75.       
76.     private int rootNum() {  
77.         int cnt = 0;  
78.         for(char key:map.keySet()) {  
79.             if(find(key) == key) {  
80.                 cnt++;  
81.             }  
82.         }  
83.         return cnt;  
84.     }  
85.       
86.     public String treeString(char root) {  
87.         Set<Character> children = childMap.get(root);  
88.         if(children == null || children.size() == 0) {  
89.             return "("+root+")";  
90.         }  
91.         StringBuilder result = new StringBuilder("("+root);  
92.         for(char child:children) {  
93.             result.append(",").append(treeString(child));  
94.         }  
95.         result.append(")");  
96.         return result.toString();  
97.     }  
98.       
99.     public char getRoot() {  
100.         return find(edges.get(0).from);  
101.     }  
102.       
103.     public static void main(String[] args) {  
104.         String input = "(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E)";  
105.         GraphEdgeTree gt = new GraphEdgeTree(input);  
106.         String error = gt.buildTree();  
107.         if(error != null) {  
108.             System.out.println(error);  
109.         } else {  
110.             String result = gt.treeString(gt.getRoot());  
111.             System.out.println(result);  
112.         }  
113.     }  
114. }

http://www.1point3acres.com/bbs/thread-131422-1-1.html

1.         class TreeNode{
2.                 char value;
3.                 TreeNode left;
4.                 TreeNode right;
5.                 TreeNode(char inp){
6.                         this.value = inp;
7.                 }
8.         }
9.         public String sExp(char[][] pair){. visit 1point3acres.com for more.
10.                 // build an adj matrix row is the parent node, col is the child node
11.                 int len = pair.length;
12.                 if (len == 0) return "";
13.                 int[][] adjMat = new int[26][26];
14.                 int[] inNode = new int[26];        // count the incoming edges of each node
15.                 int[] children = new int[26]; // count the number of children of each node
16.                 Map<Character, TreeNode> nodes = new HashMap();
17.                 TreeNode parent, child;
18.                 UnionFind myUnion = new UnionFind(26);
19.                 // build binary tree based on pair
20.                 for (int i = 0; i < len; i++){. more info on 1point3acres.com
21.                         int row = pair[i][0] - 'A';
22.                         int col = pair[i][1] - 'A';. from: 1point3acres.com/bbs 
23.                         if (children[row] == 2 && adjMat[row][col] != 1){
24.                                 // more than 2 children but not the same edge. 1point 3acres 璁哄潧
25.                                 return "E1";
26.                         }else if (adjMat[row][col] == 1){
27.                                 // duplicated edges
28.                                 return "E2";
29.                         } else if (myUnion.connected(row, col)){. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
30.                                 // if new link connect two that are already in same union there is loop
31.                                 return "E3";
32.                         }
33.                         adjMat[row][col] = 1;
34.                         children[row]++;
35.                         inNode[col]++;
36.                         myUnion.connect(row, col);
37.                         connectNodes(pair, nodes, i);
38.                 }
39.                 
40.                 // check multiple roots. 鍥磋鎴戜滑@1point 3 acres
41.                 int rNum = 0;
42.                 TreeNode root = null;
43.                 for (char x : nodes.keySet()){
44.                         if (inNode[x - 'A'] == 0){
45.                                 rNum++;
46.                                 if (rNum > 1) return "E4";
47.                                 root = nodes.get(x);
48.                         }
49.                 }
50.                 if (root == null) return "E5";
51.                 
52.                 // convert it to s-expression
53.                 return toSExpression(root);
54.         }
55.         
56.         // convert it to s-expression. 1point3acres.com/bbs
57.         String toSExpression(TreeNode root){.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
58.                 if (root == null) return "";
59.                 return "(" + root.value + toSExpression(root.left) + toSExpression(root.right) + ")";
60.         }
61.         
62.         // connect parent and child node
63.         private void connectNodes(char[][] pair, Map<Character, TreeNode> nodes,
64.                         int i) {.1point3acres缃�
65.                 TreeNode parent;
66.                 TreeNode child;
67.                 if (nodes.containsKey(pair[i][0])) parent = nodes.get(pair[i][0]);
68.                 else{.1point3acres缃�
69.                         parent = new TreeNode(pair[i][0]);
70.                         nodes.put(pair[i][0], parent);
71.                 }
72.                 if (nodes.containsKey(pair[i][1])) child = nodes.get(pair[i][1]);. 1point 3acres 璁哄潧
73.                 else{
74.                         child = new TreeNode(pair[i][1]);
75.                         nodes.put(pair[i][1], child);
76.                 }
77.                 if (parent.left == null) parent.left = child;
78.                 else {
79.                         if (parent.left.value < pair[i][1]){
80.                                 parent.right = child;
81.                         } else {
82.                                 parent.right = parent.left;. 1point 3acres 璁哄潧
83.                                 parent.left = child;
84.                         }
85.                 }
86.         }

Read full article from Buttercola: Zenefits: Validate Graph Binary Tree