BuildTree

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

/**
 * Given an input like:  
 *
 *   [2, 4]
 *   [1, 2]
 *   [3, 6]
 *   [1, 3]
 *   [2, 5]
 *
 * Use it to reconstruct this binary tree:
 *
 *                1
 *             2      3
 *          4   5  6
 *
 */

public class BuildTree {
    public static Node reconstructTree(int[][] input) {
	    // TODO: Build the tree from the values in input and return the root node.
    	if (input.length == 0)
    		return null;
    	HashMap<Integer, Node> nodes = new HashMap<Integer, Node>();
    	HashSet<Node> rootCandidates = new HashSet<Node>();
    	for (int i = 0; i < input.length; i++) {
    		int nodeVal = input[i][0];
    		if (!nodes.containsKey(nodeVal)) {
	    		Node n = new Node(nodeVal);
	    		nodes.put(nodeVal, n);
	    		rootCandidates.add(n);
    		}
    		nodeVal = input[i][1];
    		if (!nodes.containsKey(nodeVal)) {
	    		Node n = new Node(nodeVal);
	    		nodes.put(nodeVal, n);
    		}
    	}
    	for (int i = 0; i < input.length; i++) {
    		Node child = nodes.get(input[i][1]);
    		nodes.get(input[i][0]).addChild(child);
    		rootCandidates.remove(child);
    	}
    	return rootCandidates.iterator().next();
    }
    
    public static void main(String[] args) {
    	int[] n1 = {2, 4};
    	int[] n2 = {1, 2};
    	int[] n3 = {3, 6};
    	int[] n4 = {1, 3};
    	int[] n5 = {2, 5};

    	int[][] input = { n1, n2, n3, n4, n5} ;
    	System.out.println(reconstructTree(input));
    }

	static class Node {
		int val;
		Node left;
		Node right;
		public Node() {
		}
		public Node(int v) {
			val = v;
		}
		
		public void addChild(Node n) {
			if (left == null)
				left = n;
			else
				right = n;
		}
		public int hashCode() {
			return val;
		}
		
		public boolean equals(Object o) {
			Node n = (Node) o;
			return (n.val == val);
		}
		public String toString() {
			return String.valueOf(val);
		}
	}
}