CareerCup

Use Map to store the parent child relations and construct the tree,

public class TreeNode {
	public string data;
	
	public TreeNode parent;
	public TreeNode left;
	public TreeNode right;

	public TreeNode(string d) {
		data = d;
		parent = null;
		left = null;
		right = null;
	}
}

public TreeNode convertToTree(List<String> pairs)
{
	HashMap<string, TreeNode> map = new HashMap<string, TreeNode>;
	
	foreach(String pair in pairs) {
		String child = pair.Split(',').Trim();
		String parent = pair.Split(',').Trim();
		
		TreeNode ctn , ptn;
		if(!map.containsKey(child)) {
			ctn = new TreeNode(child);
			map.put(child, ctn);
		}
		if(!map.containsKey(parent)) {
			ptn = new TreeNode(parent);
			map.put(parent, ptn);
		}
		
		if(map.get(parent).left == null) {
			map.get(parent).left = ctn; 
		} else if(map.get(parent).right == null) {
			map.get(parent).right = ctn;
		} else {
			//Invalid binary tree
			return null;
		}
		map.get(child).parent = ptn;
	}
	
	Iterator it = map.entrySet().iterator();
	while(it.hasNext()) {
		Map.Entry pair = (Map.Entry) it.next();
		if(pair.getValue() == null) {
			return pair.getValue();
		}
	}
	return null;
}

Map<Integer, List<Node>> map = Maps.newHashMap();
for(Node node : input) {
	Integer parentId = node.getParentId();
	if(parentId != null) {
		List<Node> children = map.get(parentId);
		if(children == null ) {
			map.put(parentId, children = Lists.newArrayList());
		}
		children.add(node)
	}
}
return map;

I will use hashmap with a new class tree Node.

public void listToTree(List<Node> list ){
Map<Integer, NodeTree> map = new HashMap<>();
for(Node n :list){

NodeTree parentNode = map.get(n.parentId);
if(parentNode==null){
parentNode = new NodeTree();
parentNode.id=n.parentId;
parentNode.childernIds.add(n.childId);
map.put(parentNode.id, parentNode);
}
NodeTree nodeTree = map.get(n.childId);
if(nodeTree==null){
nodeTree = new NodeTree();
nodeTree.id=n.childId;
nodeTree.parentId = n.parentId;
map.put(nodeTree.id, nodeTree);
parentNode.childernIds.add(n.childId);
}else{
nodeTree.parentId=n.parentId;
}

}

}

public class NodeTree{
int parentId;
int id;
Set<Integer> childernIds= new HashSet<>();
}

class Node:
	def __init__(self, id, pid):
		self.id = id
		self.pid = pid
		
class TreeNode:
	def __init__(self, id):
		self.id = id
		self.children = []

def construct_tree_from_list(node_list):
	node_map = {u.pid : [] for u in node_list if u.pid}
	for u in node_list:
		if u.pid:
			node_map[u.pid].append(u.id)
		else:
			root = u.id
	root_node = TreeNode(root)
	q = []
	q.append(root_node)
	while q:
		node = q.pop(0)
		if node.id in node_map:
			node.children = [TreeNode(i) for i in node_map[node.id]]
		for j in range(len(node.children)):
			q.append(node.children[j])
	return root_node

public class ConvertToTree {
	
	public static void main(String[] args){
		
		ConvertToTree convertor = new ConvertToTree();


		List<Node> nodeList = new ArrayList<Node>();
		
		Node node4 = new Node(4, 2);
		Node node5 = new Node(5, 2);
		Node node2 = new Node(2, 1);
		Node node6 = new Node(6, 3);
		Node node7 = new Node(7, 3);
		Node node3 = new Node(3, 1);
		
		nodeList.add(node7);
		nodeList.add(node3);
		nodeList.add(node6);
		nodeList.add(node5);
		nodeList.add(node4);
		nodeList.add(node2);
		
		Map<Integer, NodeTree> map = new HashMap<Integer, NodeTree>();
		for(Node node : nodeList){
			
			int pId = node.parentId;
			int cId = node.nodeId;
			
			NodeTree nt1 = new NodeTree(pId);
			NodeTree nt2 = new NodeTree(cId);
			nt1.children.add(nt2);
			
			convertor.addNodeTreeToMap(map, nt1);
			
		}		
		
		NodeTree nt = convertor.mergeNodeTree(map);
		
		System.out.println(nt);
	}
	
	public void addNodeTreeToMap(Map<Integer, NodeTree> map, NodeTree nt){
		
		NodeTree nodeTree = map.get(nt.nodeId);
		if(nodeTree != null){
			nodeTree.children.addAll(nt.children);
		}else{
			Set<Integer> keys = map.keySet();
			Iterator<Integer> itr = keys.iterator();
			
			boolean added = false;
			while(itr.hasNext()){
				NodeTree nodeTree1 = map.get(itr.next());
				NodeTree nodeTree2 = nodeTree1.findNodeById(nt.nodeId);
				if(nodeTree2 != null){
					nodeTree2.children.addAll(nt.children);
					added = true;
					break;
				}
			}
			
			if(!added) map.put(nt.nodeId, nt);
		}
	}
	
	public NodeTree mergeNodeTree(Map<Integer, NodeTree> map){
		
		if(map.size()==1){
			Set<Integer> keySet = map.keySet();
			Integer key = keySet.iterator().next();
			return map.get(key);
		}
		
		List<Integer> keys = new ArrayList<Integer>(map.keySet());
		boolean[] merged = new boolean[keys.size()];
		
		for(int i=0; i<keys.size(); i++){
			if(merged[i]) continue;
			for(int j=i+1; j<keys.size(); j++){
				if(merged[j]) continue;
				
				NodeTree nt1 = map.get(keys.get(i)).findNodeById(map.get(keys.get(j)).nodeId);
				NodeTree nt2 = map.get(keys.get(j)).findNodeById(map.get(keys.get(i)).nodeId);
				
				if(nt1!=null){
					nt1.children.addAll(map.get(keys.get(j)).children);
					merged[j] = true;
				}else if(nt2!=null){
					nt2.children.addAll(map.get(keys.get(i)).children);
					merged[i]=true;
					break;
				}
				
			}
		}
		
		for(int i=0; i<merged.length; i++){
			
			if(merged[i] == true){
				
				map.remove(keys.get(i));
				
			}
			
		}
		
		return mergeNodeTree(map);		
	}
	

	
}

class NodeTree{
	int nodeId;
	List<NodeTree> children;
	
	public NodeTree findNodeById(int id){
		
		if(this.nodeId == id) return this;
		
		if(this.children==null || this.children.size()==0) return null;
		
		for(NodeTree tree : children){
			NodeTree targetTree = tree.findNodeById(id);
			if(targetTree!=null) return targetTree;
		}
		
		return null;
	}

	public NodeTree(int nodeId) {
		this.nodeId = nodeId;
		this.children = new ArrayList<NodeTree>();
	}
	
	
	public int getNodeId() {
		return nodeId;
	}
	public void setNodeId(int nodeId) {
		this.nodeId = nodeId;
	}
	public List<NodeTree> getChildren() {
		return children;
	}
	public void setChildren(List<NodeTree> children) {
		this.children = children;
	}

}

class Node{
	int nodeId;
	int parentId;
	
	public int getNodeId() {
		return nodeId;
	}
	public void setNodeId(int nodeId) {
		this.nodeId = nodeId;
	}
	public int getParentId() {
		return parentId;
	}
	public void setParentId(int parentId) {
		this.parentId = parentId;
	}
	public Node(int nodeId, int parentId) {
		this.nodeId = nodeId;
		this.parentId = parentId;
	}

}

// TimeComplexity O(N) where no is the no of nodes

class Node {

                Integer nodeId;
                Integer parentNodeId;
                
                public Integer getNodeId() {
                        return nodeId;
                }
                
                public void setNodeId(Integer nodeId) {
                        this.nodeId = nodeId;
                }
                
                public Integer getParentNodeId() {
                        return parentNodeId;
                }
                
                public void setParentNodeId(Integer parentNodeId) {
                        this.parentNodeId = parentNodeId;
                }
        }

        class TreeNode {

                Integer nodeId;
                List<TreeNode> childs;

                TreeNode(Integer id) {

                        this.nodeId = id;
                        childs = new ArrayList<TreeNode>();
                }

                public Integer getNodeId() {
                        return nodeId;
                }

                public void setNodeId(Integer nodeId) {
                        this.nodeId = nodeId;
                }

                public List<TreeNode> getChilds() {
                        return childs;
                }

                public void setChilds(List<TreeNode> childs) {
                        this.childs = childs;
                }

        }

        TreeNode createTree(List<Node> listOfNode) {

                Map<Integer, List<Node>> parentChildRelationShipMap = new HashMap<Integer, List<Node>>();
                Map<Integer, Node> nodeIdMap = new HashMap<Integer, TestClass.Node>();
                Integer rootId = null;
                for (Node node : listOfNode) {
                        Integer parentId = node.getParentNodeId();
                        Integer nodeId = node.getNodeId();
                        if (null != parentChildRelationShipMap.get(nodeId)) {
                                nodeIdMap.put(nodeId, node);
                                if (null != parentChildRelationShipMap.get(parentId)) {
                                        parentChildRelationShipMap.get(parentId).add(node);
                                } else {
                                        ArrayList<Node> nodeList = new ArrayList<Node>();
                                        nodeList.add(node);
                                        parentChildRelationShipMap.put(parentId, nodeList);
                                }
                        } else {
                                parentChildRelationShipMap.put(nodeId, new ArrayList<Node>());
                                nodeIdMap.put(nodeId, node);
                        }
                        
                        if(null == parentId) {
                                rootId = nodeId;
                        }
                }

                return createTreeUtils(parentChildRelationShipMap, rootId);
                
        }
        
        TreeNode createTreeUtils(Map<Integer, List<Node>> parentChildRelationShipMap, Integer nodeId) {

                List<TreeNode> childList = new ArrayList<TreeNode>();
                for (Node node : parentChildRelationShipMap.get(nodeId)) {
                        childList.add(createTreeUtils(parentChildRelationShipMap, node.getNodeId()));
                }

                TreeNode node = new TreeNode(nodeId);
                node.setChilds(childList);

                return node;
        }