CareerCup

public class TreePrinter {
	
	public static void main(String[] args) {
		List<Relation> input = new ArrayList<Relation>();
		input.add(new Relation("animal","mammal"));
		input.add(new Relation("animal","bird"));
		input.add(new Relation("lifeform","animal"));
		input.add(new Relation("cat","lion"));
		input.add(new Relation("mammal","cat"));
		input.add(new Relation("animal","fish"));
		
		TreePrinter t = new TreePrinter();
		t.printTree(input);
	}
	
	public void printTree(Iterable<Relation> rs){
		
		//build a tree like below with lifeform as root 
		//and do a traversal.
		//lifeform -- animal
		//animal -- mammal -- cat-- lion
		//animal -- bird
		//animal -- fish
		
		//use this set to keep track of children to find out 
		//which one is the root node.
		Set<String> setOfNotRootElements = new HashSet<String>();
		
		//build a tree using HashMap. You can also build the tree 
		//put a Map inside a Map, but this seems simpler.
		HashMap<String, List<String>> map = new HashMap<String, List<String>>();
		for(Relation r: rs){
			List<String> children =  new ArrayList<String>();
			if(map.containsKey(r.parent)){
				children = map.get(r.parent);
			}
			children.add(r.child);
			map.put(r.parent, children );
			
			//keeping track of children..
			setOfNotRootElements.add(r.child);
		}
		
		//find the root
		Set<String> diffSet = new HashSet<String>(map.keySet());
		diffSet.removeAll(setOfNotRootElements);
		String root = diffSet.iterator().next();
		
		//traverse the tree.
		printNode(root, map);
		
		//lifeform
		//animal
		//mammal
		//cat
		//lion
		//bird
		//fish
	}
	
	public void printNode(String parent, HashMap<String, List<String>> map){
		System.out.println(parent);
		List<String> children = map.get(parent);
		if(children != null){
			for(String child: children){
				printNode(child, map);
			}
		}
	}
 
}

C++

#include<hash_map>
#include<string>
#include<list>
#include<set>
#include<stack>
using namespace std;

class Relation { 
public:
	string parent; 
	string child; 
public:
	Relation(string parent, string child) { this->parent = parent; this->child = child;} 
};

class TreePrinter { 
public:
	
	
	static void printTree(list<Relation> rs) { 
		hash_map<string, set<string>> myNodes;
		set<string> headers;
		list<Relation>::iterator it = rs.begin();
		for(; it != rs.end(); it++)
		{
			hash_map<string, set<string>>::iterator temp = myNodes.find(it->parent);
			if(temp != myNodes.end())
			{
				temp->second.insert(it->child);
			}
			else
			{
				headers.insert(it->parent);
				set<string> child;
				child.insert(it->child);
				myNodes.insert(pair<string, set<string>>(it->parent,child));
			}
			temp = myNodes.find(it->child);
			if(temp != myNodes.end())
			{
				headers.erase(it->child);
			}
			else if(temp == myNodes.end())
			{
				set<string> child;
				myNodes.insert(pair<string, set<string>>(it->child,child));
			}
		}
		stack<string> printSequece;
		int count = 1;
		//
		for(set<string>::iterator elem = headers.begin(); elem != headers.end(); elem++)
		{
			printSequece.push(*elem);
		}
			while(!printSequece.empty())
			{
				string current = printSequece.top();
				printf("line %d, %s\n",count++, current.c_str());
				printSequece.pop();
				set<string> childs = myNodes[current];
				for(set<string>::iterator child= childs.begin(); child != childs.end(); child++)
				{
					printSequece.push(*child);
				}

			}
	

	} 
};

package careercup;

import java.util.*;

/**
 * Date: 08.10.13
 * Time: 01:14
 */
public class TreePrinter {

    public static void printTree(Iterable<Relation> rs) {

        class Tree {
            String node;
            List<Tree> child = new ArrayList<Tree>();

            public Tree(String nodeName) {
                node = nodeName;
            }

            Tree find(String nodeName) {
                if (node.equals(nodeName)) {
                    return this;
                } else {
                    for (Tree tree : child) {
                        Tree result = tree.find(nodeName);
                        if (result != null) {
                            return result;
                        }
                    }
                }

                return null;
            }

        }


        Tree root = null;
        Relation r = null;

        Iterator<Relation> it = rs.iterator();

        PriorityQueue<Relation> queue = new PriorityQueue<Relation>();


        while( it.hasNext() ) {

            r = it.next();

            if (root == null) {
                root = new Tree(r.parent);
                root.child.add(new Tree(r.child));
            } else {
                Tree parent = root.find(r.parent);
                if (parent != null) {
                    parent.child.add(new Tree(r.child));
                } else {
                    parent = root.find(r.child);
                    if (parent == root) {
                        Tree newRoot = new Tree(r.parent);
                        newRoot.child.add(root);
                        root = newRoot;
                    } else {
                        queue.add(r);
                    }
                }
            }

            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                r = queue.poll();

                Tree parent = root.find(r.parent);
                if (parent != null) {
                    parent.child.add(new Tree(r.child));
                } else {
                    parent = root.find(r.child);
                    if (parent == root) {
                        Tree newRoot = new Tree(r.parent);
                        newRoot.child.add(root);
                        root = newRoot;
                    } else {
                        queue.add(r);
                    }
                }
            }

        }

        while (!queue.isEmpty()) {
            r = queue.poll();

            Tree parent = root.find(r.parent);
            if (parent != null) {
                parent.child.add(new Tree(r.child));
            } else {
                parent = root.find(r.child);
                if (parent == root) {
                    Tree newRoot = new Tree(r.parent);
                    newRoot.child.add(root);
                    root = newRoot;
                } else {
                    queue.add(r);
                }
            }
        }


        Stack<Tree> stack = new Stack<Tree>();
        stack.push(root);

        int i = 1;
        while(!stack.empty()) {
            Tree currentTree = stack.pop();
            System.out.println(i++ + ". " + currentTree.node);

            for (int j = currentTree.child.size() - 1; j >= 0; --j) {
                stack.push(currentTree.child.get(j));
            }
        }

    }


    static class Relation implements Comparable<Relation>{
        String parent, child;

        public Relation(String parent, String child) {
            this.parent = parent;
            this.child = child;
        }

        @Override
        public int compareTo(Relation o) {
            return 0;
        }
    }


    public static void main(String[] arg) {

        List<Relation> input = new ArrayList<Relation>();

        input.add(new Relation("animal", "mammal"));
        input.add(new Relation("animal", "bird"));
        input.add(new Relation("lifeform", "animal"));
        input.add(new Relation("cat", "lion"));
        input.add(new Relation("mammal", "cat"));
        input.add(new Relation("animal", "fish"));

        TreePrinter.printTree(input);


    }

}

package careercup;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class TreePrinter {
	public static void printTree(Iterable<Relation> rs) {
		class Node {
			final String name;
			final List<Node> children = new LinkedList<Node>();

			public Node(String name) {
				this.name = name;
			}
		}

		Map<String, Node> nodeDictionary = new HashMap<String, Node>();
		Set<Node> roots = new HashSet<Node>();

		for (Relation r : rs) {
			if (!nodeDictionary.containsKey(r.parent)) {
				Node node = new Node(r.parent);
				nodeDictionary.put(r.parent, node);
				roots.add(node);
			}
			if (!nodeDictionary.containsKey(r.child)) {
				Node node = new Node(r.child);
				nodeDictionary.put(r.child, node);
			}
			Node parentNode = nodeDictionary.get(r.parent);
			Node childNode = nodeDictionary.get(r.child);

			// i want to print the fish last
			parentNode.children.add(0, childNode);
			roots.remove(childNode);
		}
		Stack<Node> stack = new Stack<Node>();
		stack.addAll(roots);
		int line = 1;
		while(!stack.isEmpty()){
			Node pop = stack.pop();
			System.out.println(String.format("line %d : %s", line++, pop.name));
			
			for(Node child : pop.children) {
				stack.push(child);
			}
		}
	}

	public static class Relation {
		String parent;
		String child;

		public Relation(String parent, String child) {
			this.parent = parent;
			this.child = child;
		}
	}

	public static void main(String[] args) {
		List<Relation> input = new ArrayList<Relation>();

		input.add(new Relation("animal", "mammal"));
		input.add(new Relation("animal", "bird"));
		input.add(new Relation("lifeform", "animal"));
		input.add(new Relation("cat", "lion"));
		input.add(new Relation("mammal", "cat"));
		input.add(new Relation("animal", "fish"));

		TreePrinter.printTree(input);
		// Expected output:
		// line 1: lifeform
		// line 2: animal
		// line 3: mammal
		// line 4: cat
		// line 5: lion
		// line 6: bird
		// line 7: fish
	}
}

Do we can use a prefix tree?

Will look like:-


[root]------------------------------------
| | |
lion | |
\ | |
cat | |
| | |
mammal bird fish
\ | |
animal---------|----------------|
|
lifeform

Do we can use a prefix tree?

Will look like:-

------------------[root]------
------|--------------|-------- |
-----lion-----------|-------- |
------|--------------|---------|
------cat-----------|-------- |
------|--------------|-------- |
----mammal--- bird----- fish
------|--------------|----------|
-----animal-------|----------|
------|
lifeform

package com.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class TestDelete {

  public static void main(String[] args) {
    List<Relation> input = new ArrayList<Relation>();

    input.add(new Relation("animal", "mammal"));
    input.add(new Relation("animal", "bird"));
    input.add(new Relation("lifeform", "animal"));
    input.add(new Relation("cat", "lion"));
    input.add(new Relation("mammal", "cat"));
    input.add(new Relation("animal", "fish"));

    TestDelete.printTree(input);
  }

  public static void printTree(Iterable<Relation> rs) {
    HashMap<String, List<Edge>> graph = new HashMap<String, List<Edge>>();

    for (Relation r : rs) {
      if (!graph.containsKey(r.parent)) {
        graph.put(r.parent, new ArrayList<Edge>());
      }

      graph.get(r.parent).add(new Edge(r.parent, r.child));
    }

    String start = findRoot(graph);
    printAll(graph, start);
  }

  private static void printAll(HashMap<String, List<Edge>> graph, String start) {
    if (start == null)
      return;
    System.out.println(start);
    List<Edge> edges = graph.get(start);
    if (edges == null)
      return;
    for (Edge e : edges) {
      printAll(graph, e.getDestNode());
    }

  }

  private static String findRoot(HashMap<String, List<Edge>> graph) {
    List<String> root = new ArrayList<String>(graph.keySet());
    for (List<Edge> edges : graph.values()) {
      for (Edge e : edges)
        root.remove(e.getDestNode());
    }
    return root.get(0);
  }

  static class Edge {
    String srcNode;
    String destNode;

    public Edge(String s, String d) {
      srcNode = s;
      destNode = d;
    }

    public String getSrcNode() {
      return srcNode;
    }

    public String getDestNode() {
      return destNode;
    }
  }

  static class Relation {
    String parent;
    String child;

    public Relation(String parent, String child) {
      this.parent = parent;
      this.child = child;
    }
  }
}

package exam;

import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) throws java.lang.Exception {
		List<Relation> input = new ArrayList<Relation>();
		input.add(new Relation("animal", "mammal"));
		input.add(new Relation("animal", "bird"));
		input.add(new Relation("lifeform", "animal"));
		input.add(new Relation("cat", "lion"));
		input.add(new Relation("mammal", "cat"));
		input.add(new Relation("animal", "fish"));

		printTree(input);
	}

	public static void printTree(List<Relation> input) {
		if (!input.isEmpty()) {
			Relation head = input.remove(0);
			List<Relation> parents = new ArrayList<>();
			List<Relation> children = new ArrayList<>();
			List<Relation> friends = new ArrayList<>();
			List<Relation> rest = new ArrayList<>();
			for (Relation relation : input) {
				if (relation.child.equals(head.parent))
					parents.add(relation);
				else if (relation.parent.equals(head.child))
					children.add(relation);
				else if (relation.parent.equals(head.parent))
					friends.add(relation);
				else
					rest.add(relation);
			}

			if (parents.isEmpty())
				System.out.println(head.parent);
			else {
				parents.addAll(rest);
				printTree(parents);
			}
			for (Relation relation : friends) {
				System.out.println(relation.child);
			}
			if (children.isEmpty()) {
				System.out.println(head.child);
			} else {
				children.addAll(rest);
				printTree(children);
			}
		}
	}

	static class Relation {
		String parent, child;

		public Relation(String parent, String child) {
			this.parent = parent;
			this.child = child;
		}
	}
}

a bit verbose but simple to follow (I hope)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TreePrinter {

  public static void main(String[] args) {
    List<Relation> input = new ArrayList<>();

    input.add(new Relation("animal", "mammal"));
    input.add(new Relation("animal", "bird"));
    input.add(new Relation("lifeform", "animal"));
    input.add(new Relation("cat", "lion"));
    input.add(new Relation("mammal", "cat"));
    input.add(new Relation("animal", "fish"));
    TreePrinter.printTree(input);

  }

  public static void printTree(Iterable<Relation> rs) {
    Map<String, Node<String>> nodesByName = new HashMap<>();
    for (Relation r : rs) {
      String parent = r.parent;
      String child = r.child;

      Node<String> parentNode;
      Node<String> childNode;

      if (nodesByName.containsKey(parent)) {
        parentNode = nodesByName.get(parent);
      } else {
        parentNode = new Node<String>(parent);
        nodesByName.put(parent, parentNode);
      }

      if (nodesByName.containsKey(child)) {
        childNode = nodesByName.get(child);
      } else {
        childNode = new Node<String>(child);
        nodesByName.put(child, childNode);
      }


      if (parentNode != null && !parentNode.children.contains(childNode)) {
        parentNode.addChild(childNode);
      }
    }
    nodesByName.values().iterator().next().getRoot().dfsPrint();
  }

  public static class Relation {
    String parent;
    String child;

    public Relation(String parent, String child) {
      this.parent = parent;
      this.child = child;
    }
  }

  public static class Node<T> {
    private Node<T> parent;
    private List<Node<T>> children = new ArrayList<>();
    private T data;

    public Node(T data) {
      this.data = data;
    }

    public T getData() {
      return data;
    }

    public void setData(T data) {
      this.data = data;
    }

    public Node<T> addChild(T data) {
      Node<T> node = new Node<>(data);
      node.parent = this;
      children.add(node);
      return node;
    }

    public Node<T> addChild(Node<T> node) {
      node.parent = this;
      children.add(node);
      return node;
    }


    public Node<T> getRoot() {
      if (parent == null) {
        return this;
      } else {
        return parent.getRoot();
      }
    }

    public void dfsPrint() {
      if (data != null) {
        System.out.println(data.toString());
      }
      for (Node<T> child : children) {
        child.dfsPrint();
      }

    }
  }
}

public static void printTree(Iterable<Relation> rs) { 
	        ArrayList<String> Nodes = new ArrayList<String> ();
	        ArrayList<String> Parents = new ArrayList<String> ();
	        HashMap <String, ArrayList<String>> map = new HashMap <String, ArrayList<String>>();
	        
	        for(Relation r : rs) {
	            String p = r.parent;
	            String c = r.child;
	            if(!Nodes.contains(p)) {
	                Parents.add(p);
	                Nodes.add(p);
	            }
	            
	            if(Nodes.contains(c)) {
	                Parents.remove(c);
	            } else {
	                Nodes.add(c);
	            }
	            
	            if(map.containsKey(p)) {
	                ArrayList<String> childs = map.get(p);
	                childs.add(c);
	                map.put(p, childs);
	            } else {
	                ArrayList<String> childs = new ArrayList<String>();
	                childs.add(c);
	                map.put(p, childs);
	            }
	        }

	        String key = Parents.get(0);
	        System.out.println(key);
	        ArrayList<String> que = new ArrayList<String>();
	        que.add(key);
	        while(que.size() != 0) {
	            String s = que.remove(0);
	            if(map.containsKey(s)) {
	                ArrayList<String> childs = map.get(s);
	                int i;
	                for(i = 0; i < childs.size(); i++) {
	                    System.out.print(childs.get(i) + " ");
	                    que.add(childs.get(i));
	                }
	                System.out.println();
	            }
	        }
	}

{{
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class TreePrinter {
public static class Relation {
String parent;
String child;

public Relation(String parent, String child) {
this.parent = parent;
this.child = child;
}
}

public static void print(int i, String key) {
System.out.println("line " + i + ": " + key);
}

public static class Node{
String key;
Node parent;
List<Node> childlen;
Node(String key){
this.key = key;
childlen = new LinkedList<Node>();
}
public int printOut(int i){
print(i,key);
i++;
for(Node child:childlen){
i = child.printOut(i);
}
return i;
}
}
public static void printTree(Iterable<Relation> rs) {
// your code
Map<String, Node> map = new LinkedHashMap<String, Node>();
for (Relation r : rs) {
Node parent = map.get(r.parent);
if(parent == null){
parent = new Node(r.parent);
map.put(r.parent, parent);
}
Node child = map.get(r.child);
if(child == null){
child = new Node(r.child);
map.put(r.child, child);
}
parent.childlen.add(child);
child.parent = parent;
}
int index = 1;
for (String key : map.keySet()) {
if (map.get(key).parent == null) {
index = map.get(key).printOut(index);
}
}
}

public static void main(String[] argv) {
List<Relation> input = new ArrayList<Relation>();
input.add(new Relation("animal", "mammal"));
input.add(new Relation("animal", "bird"));
input.add(new Relation("lifeform", "animal"));
input.add(new Relation("cat", "lion"));
input.add(new Relation("mammal", "cat"));
input.add(new Relation("animal", "fish"));
printTree(input);
}
}

}}

public static void printTree(Iterable<Relation> rs) {
        
        Set<String> roots = new HashSet<String>();
        Map<String,List<String>> adjMap = new HashMap<String, List<String>>();
        for(Relation r : rs) {
            List<String> children = adjMap.get(r.parent);
            if(children==null) {
                children = new ArrayList<String>();
                adjMap.put(r.parent, children);
            }
            children.add(r.child);
            roots.add(r.parent);
            roots.remove(r.child);
        }

        String root = roots.iterator().next();

        if(root == null) {
            throw new IllegalStateException("No root found");
        }

        System.out.println("AdjMap: " + adjMap);

        Stack<String> queue = new Stack<String>();
        String node = null;
        queue.add(root);
        while(!queue.isEmpty()) {
            node = queue.pop();
            System.out.println(node);
            if(!adjMap.containsKey(node)) continue;
            List<String> list = adjMap.get(node);
            for(int i = list.size() - 1; i>=0; --i) {
                queue.push(list.get(i));
            }
        }

    }

I love first solution. Anyway, I have implemented the other option, creating a homemade TreeNode quite simple.

public class TreeNode {
	ArrayList<TreeNode> children = new ArrayList<TreeNode>();
	String data;
	
	public TreeNode(String d){
		data = d;
	}
}

public class TreePrinter {

	public static void main(String[] args) {
		List<Relation> input = new ArrayList<Relation>();
		input.add(new Relation("animal","mammal"));
		input.add(new Relation("animal","bird"));
		input.add(new Relation("lifeform","animal"));
		input.add(new Relation("cat","lion"));
		input.add(new Relation("mammal","cat"));
		input.add(new Relation("animal","fish"));
		
		TreePrinter t = new TreePrinter();
		t.printTree(input);
	}
	
	public void printTree (Iterable<Relation> rs){
		// First we create a tree with a dummy root, every node without parent
		//  will be its children until a parent appears
		TreeNode tree = new TreeNode(""); 
		
		TreeNode parent;
		for (Relation rel: rs){
			parent = searchNode(rel.parent, tree);
			if(parent == null){// the parent it is not in the tree
				parent = new TreeNode(rel.parent);
				tree.children.add(parent);
			}

			// If the children previously existed but without parent, (child of the root)
			// Update its new place
			boolean flag = false;
			for(TreeNode child: tree.children){
				if(child.data.equals(rel.child)){
					parent.children.add(child);
					tree.children.remove(child);
					flag = true;
				}
			}
			if(!flag){
				TreeNode child = new TreeNode(rel.child);
				parent.children.add(child);
			}
		}
		
		printNode(tree);
		
	}
	
	public void printNode (TreeNode node){
		System.out.println(node.data);

		for(TreeNode child: node.children){
			printNode(child);
		}
	}
	
	// Classic dfs search 
	public TreeNode searchNode(String s, TreeNode t){
		if(t == null) return null;
		if(t.data.equals(s)) return t;
		
		TreeNode auxNode;
		for(TreeNode child: t.children){
			auxNode = searchNode(s, child);
			if(auxNode != null) return auxNode;
		}
		return null;
	}
}

Is it making a tree from list and then doing dfs.?