CareerCup

Assuming input is a list of strings each of the form "a,b"

public class TreeNode
        {
            public TreeNode parent;
            public string value;
            public List<TreeNode> children;

            public TreeNode(string value)
            {
                this.value = value;
                this.parent = null;
                children = new List<TreeNode>();
            }
        }

        public TreeNode ConvertCSPairsToTree(List<string> pairs)
        {
            Dictionary<string, TreeNode> nodeNameToNodeMap = new Dictionary<string, TreeNode>();

            foreach (string pair in pairs)
            {
                string child = pair.Split(',')[0].Trim();//a from a,b
                string parent = pair.Split(',')[1].Trim();//b from a,b

                if (!nodeNameToNodeMap.ContainsKey(child))
                    nodeNameToNodeMap[child] = new TreeNode(child);
                if (!nodeNameToNodeMap.ContainsKey(parent))
                    nodeNameToNodeMap[parent] = new TreeNode(parent);

                nodeNameToNodeMap[parent].children.Add(nodeNameToNodeMap[child]);//add a to b's children
                nodeNameToNodeMap[child].parent = nodeNameToNodeMap[parent];//mark a as b's child
            }

            //find the node that doesn't have a parent. that is the root node.
            foreach (string nodeName in nodeNameToNodeMap.Keys)
            {
                if (nodeNameToNodeMap[nodeName].parent == null)
                    return nodeNameToNodeMap[nodeName];
            }

            return null;//there was a cycle or the input list was empty
        }

// for pair i, the child is children[i], parent is parents[i]
    public BinaryTreeNode convert(int[] children, int[] parents) {
        HashMap<Integer, BinaryTreeNode> nodes = new HashMap<>();

        // resolve root
        int rootValue = this.getRootValue(children, parents);
        BinaryTreeNode root = new BinaryTreeNode(rootValue);
        nodes.put(rootValue, root);

        for(int i = 0; i < children.length; i ++) {
            int child = children[i];

            BinaryTreeNode childNode = nodes.get(child);
            if(childNode == null) {
                childNode = new BinaryTreeNode(child);
                nodes.put(child, childNode);
            }

            int parent = parents[i];
            BinaryTreeNode parentNode = nodes.get(parent);
            if(parentNode == null) {
                parentNode = new BinaryTreeNode(parent);
                nodes.put(parent, parentNode);
            }
            // set parent child relationship
            childNode.setParent(parentNode);
            if(parentNode.getLeftChild() == null)
                parentNode.setLeftChild(childNode);
            else
                parentNode.setRightChild(childNode);
        }

        return root;
    }



    private int getRootValue(int[] children, int[] parents) {
        HashSet<Integer> ancestors = new HashSet<>();
        for(int parent : parents)
            ancestors.add(parent);
        for(int child : children)
            ancestors.remove(child);
        return ancestors.iterator().next();
    }

import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * Objective: To return root node, given pairs of child, parent nodes
 * of the tree.
 * 
 * @author Sunil
 *
 */
public class Node {

	HashSet<Node> children = new HashSet<Node>();
	boolean hasParent = false;
	int data;

	public static void main(String[] args) {
		// Sample input
		Node root = constructTree(new String[]{"3,2","4,2","7,5","8,5","2,1","5,1"});
		System.out.println("Root node: "+root.data);
	}

	private static Node constructTree(String[] strings) {
		if(strings == null) {
			System.out.println("Provide tree input!");
			return null;
		}
		HashMap<Integer, Node> nodeMap = new HashMap<Integer, Node>();
		for (int i = 0; i < strings.length; i++) {
			try {
				StringTokenizer str = new StringTokenizer(strings[i],",");
				int child = Integer.parseInt(str.nextToken());
				int parent = Integer.parseInt(str.nextToken());
				Node c = nodeMap.get(child);
				if(c == null) { // Node not yet added
					c = new Node();
					c.data = child;
					nodeMap.put(child, c);
				}
				Node p = nodeMap.get(parent);
				if(p == null) { // Node not yet added
					p = new Node();
					p.data = parent;
				}
				// Add child to parent node
				c.hasParent = true;
				p.children.add(c);				
				nodeMap.put(parent, p);		
			} catch(Exception ex) {
				System.out.println("Invalid tree input!");
				return null;
			}
		}
		for(Node node: nodeMap.values()) {
			if(!node.hasParent)
				return node; // Found the root
		}
		return null; // If root not found return null
	}
}