CareerCup

1) Map each input like Map<Integer, List<Integer>>; key - parentId, value children's list.
2) Recursively reconstruct the tree.
Code:

public static void main(String[] args) {
	int[][] nodes = { { 2, 4 }, { 1, 2 }, { 3, 6 }, { 1, 3 }, { 2, 5 } };
	Map<Integer,List<Integer>> treeMap = new HashMap<Integer,List<Integer>>();
	Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
	int rootCandidate = nodes[0][0];
	for (int i = 0; i < nodes.length; i++) {
	    List<Integer> children = null;
	    if (treeMap.containsKey(nodes[i][0])) {
			children = treeMap.get(nodes[i][0]);
	    } else {
			children = new ArrayList<Integer>();
			treeMap.put(nodes[i][0], children);
	    }
	    children.add(nodes[i][1]);
	    childParentMap.put(nodes[i][1], nodes[i][0]);
	}
	while(childParentMap.containsKey(rootCandidate)) {
	    rootCandidate = childParentMap.get(rootCandidate);
	}
	System.out.println(reconstructTree(treeMap, rootCandidate));
}

public static Node reconstructTree(Map<Integer, List<Integer>> treeMap, int v) {
	Node root = new Node(v);
	if (treeMap.get(v) == null || treeMap.get(v).isEmpty()) {
		return root;
	}
	root.left = reconstructTree(treeMap, treeMap.get(v).get(0));
	if (treeMap.get(v).size() == 2) {
		root.right = reconstructTree(treeMap, treeMap.get(v).get(1));
	}
	return root;
}

-Create Map<int, Node*> m
for each entry in given list
check if first int is available in map
if yes, create the child and and it to left if left if null else to the right
if it is not available, create root, create child and assign as left child and add to Map

you can find the root and return it.

1. Imagine a list containing root of trees. For example, if we find an element (1,2) and next (3,4). We store them as two trees with roots 1 & 3.
2. So, as soon as we traverse through a list, we check the parent and child present in each treelist.
3. If parent and child both not found in any tree, append the tree in the list with parent as root.
3. If parent found and child not found in any tree, append the child to left or right of parent by checking.
4. If parent not found and child found in tree (child will be obviously in the root of the tree in the list, if not, then child already has parent -- not possible throw exception, not implemented in the code below),
5. If parent and child found, make child as left or right child of parent by checking, remove the child from the list of trees.

public static Node createTree(int[][] nodes){
	//newList will hold non-linked trees. For example,
	//if first element is (1,2) and next is (3,4) 
	//separate tree for (1,2) and (3,4) are created and root is stored in newList as an array of 
	//Tree. 
	ArrayList<Node> newList=new ArrayList<Node>();
	for(int i=0;i<nodes.length;i++){
		Node parent = findNode(newList, nodes[i][0]);
		Node child = findChild(newList,nodes[i][1]);
		//parent has not been found till now
		if(parent==null){
			parent = new Node(nodes[i][0]); 
			//child not found till now, create a new tree with parent as root and store in
			// newList
			if(child==null){
				child = new Node(nodes[i][1]);
				parent.left=child;
			}
			//child found in the newList but not parent if child found it will be always in the
			// root
			else{
				parent.left=child;
				newList.remove(child);
			}
			newList.add(parent);
		}
		else{
			//parent exists -- two cases
			//case 1: parent already has a left child
			//case 2: parent is already a child of some Node
			if(child==null){
				child = new Node(nodes[i][1]);
				if(parent.left==null)
					parent.left=child;
				else
					parent.right=child;
			}
			//both parent and child exists
			//child will be on top in newList. So, add it to parent and remove child from
			// newlist
			else{
				if(parent.left==null)
					parent.left=child;
				else
					parent.right=child;
				newList.remove(child);
			}
		}
	}
	return newList.get(0);
}
public static Node findNode(ArrayList<Node> list, int element){
	if(list==null)
		return null;
	for(int i=0;i<list.size();i++){
		Node node = list.get(i);
		Node found = find(node, element);
		if(found!=null)
			return found;
	}
	return null;
}
	
public static Node findChild(ArrayList<Node> list, int element){
	if(list==null)
		return null;		
	for(int i=0;i<list.size();i++){
		Node node = list.get(i);
		if(node.data == element)
			return node;
	}
	return null;
}

public static Node find(Node root, int element){
	if(root==null)
		return null;
	if(root.data==element)
		return root;
	Node node = find(root.left,element);
	if(node!=null)
		return node;
	node = find(root.right,element);
	if(node!=null)
		return node;
	return null;
}

It can be done by keeping following type of map:
map<int, pair<tree*, tree*> >
Key: node's key
pair.first = Tree node of Parent of Key
pair.second = Tree Node of Key

parsing each input line, if key exist then update its parent and child else add key to map.

pair<int, int> input[]; // Input data
tree *root = NULL;
tree* binaryTree::constructBinaryTree ()
{
        map<int, pair<tree*, tree*> > keyParentNode;    //Interger: key, pair.second: treenode of key, pair.first: parent of pair.second

        tree *node = NULL;
        pair<tree*, tree*> P(NULL,NULL);
        pair<tree*, tree*> C(NULL,NULL);
        int i = 0;
        int size = input.size();
        map<int, pair<tree*, tree*> >::iterator mapIt;
        for (i = 0; i < size; i++)
        {
                mapIt = keyParentNode.find(input[i].first);//First value of input pair
                if (mapIt == keyParentNode.end())
                {
                        node = new tree;
                        node->key = input[i].first;
                        node->left = NULL;
                        node->right = NULL;
                        keyParentNode[input[i].first] = pair<tree*, tree*>(NULL, node);
                }
                P = keyParentNode[input[i].first];

                mapIt = keyParentNode.find(input[i].second);//Second value of input pair
                if (mapIt == keyParentNode.end())
                {
                        node = new tree;
                        node->key = input[i].second;
                        node->left = NULL;
                        node->right = NULL;
                        keyParentNode[input[i].second] = pair<tree*, tree*>(NULL, node);
                }
                C = keyParentNode[input[i].second];

                if (P.second->left == NULL)
                {
                        P.second->left = C.second;
                }
                else
                {
                        P.second->right = C.second;
                }
                C.first = P.second; //Storing Parent Node
        }

        for (mapIt = keyParentNode.begin(); mapIt != keyParentNode.end(); mapIt++)
        {
                if ((mapIt->second).first == NULL)
                {
                        root = (mapIt->second).second; // return root of tree
                        break;
                }
        }
        return root;

You can as well represent a tree in an array

for node i, left child is 2i+1 and right child is 2i+2

An array is always sorted -

void insert(int tree[], int size, int n, int x)
{

	if( n == size )
		return; // error

	// n is number of elems currently in a tree
	for(i = n; i >=0 ; i++)
	{
		if( x < a[i] )
			a[i+1] = a[i];
	}
	a[i] = x;
}

1. create a matrix like in this case
6* 6 matrix
2. traverse the matrix in DFS manner and create a binary tree accordingly

There are so many good solutions here but I want to share mine too ok?
Suggestions are always welcome.

#include <iostream>
#include <memory>
#include <map>
#include <vector>
#include <utility>

template <typename T>
struct node {
	node(T value) : value_{value}, right_{nullptr}, left_{nullptr} {}
	~node() { delete(right_); delete(left_); }
	T value_;
	node<T>* right_;
	node<T>* left_;
};

template <typename T>
void in_order_traversal(node<T>* nd) {
	if(nd == nullptr)
		return;

	in_order_traversal(nd->left_);
	in_order_traversal(nd->right_);
	std::cout << nd->value_ << std::endl;
}

int main() {
	std::vector<std::pair<int,int> > vec {{2,4}, {1,2}, {3,6}, {1,3}, {2,5}};
	std::map<int, node<int> *> nodesmap;
	node<int>* root = nullptr;
	
	for(auto p: vec) {
		std::map<int, node<int>*>::iterator itsrc;
		std::map<int, node<int>*>::iterator itdest;

		itsrc = nodesmap.find(p.first);
		itdest = nodesmap.find(p.second);
		
		node<int>* src = nullptr;
		node<int>* dest = nullptr;

		if(itsrc != nodesmap.end())
			src = itsrc->second;
		else
			src = new node<int>(p.first);
		
		if(itdest != nodesmap.end())
			dest = itdest->second;
		else
			dest = new node<int>(p.second);

		std::cout << "src:" << src->value_ << " "
			  << "dest:" << dest->value_ << std::endl;

		if(src->left_ == nullptr)
			src->left_ = dest;
		else
			src->right_ = dest;

		nodesmap.insert(std::pair<int, node<int>*>(p.first, src));
		nodesmap.insert(std::pair<int, node<int>*>(p.second, dest));
	}

	std::map<int, node<int>*>::iterator it = nodesmap.find(1);
	if(it != nodesmap.end()) {
			root = it->second;			
			in_order_traversal<int>(root);
	}
	return 0;
}

In my algorithm : Each node also contains an additional pointer to its parent, not just the left and right child.
recontstructTree() is called for each pair of numbers.
Traverse() does a pre-order traversal of the tree and prints the resulting tree.
I have tested the code and it works fine. Let me know if any questions.

class BuildTree {
	static HashMap<Integer,Node> nodes = new HashMap<Integer,Node>();
	static Node root = null;
	
    static class Node
    {
        Node right;
        Node left;
        Node parent;
        int num;
        
        public Node(int number)
        {
            left = null;
            right = null;
            parent = null;
            num = number;
        }
    }
    
  public static Node reconstructTree(int[][] input) {
    // TODO: Build the tree from the values in input and return the root node.
    Integer x = new Integer(input[0][0]);
    Integer y = new Integer(input[0][1]);
    Node parent = null;
    Node child = null;
    
    if(!nodes.containsKey(x)) 
    {
    	parent = new Node(x);
    	nodes.put(x, parent);
    }
    
    if(!nodes.containsKey(y))
    {
    	child  = new Node(y);
    	nodes.put(y, child);
    }
    parent = nodes.get(x);
    child = nodes.get(y);
    
    if(parent.left==null){
    	parent.left = child;
    	System.out.println(child.num +" is attached as Left child to "+ parent.num);
    }
    else if(parent.right==null){
        parent.right = child;
        System.out.println(child.num +" is attached as right child to "+ parent.num);
    }
    if(child.parent== null) {
    	child.parent = parent;
    	root = parent;
    }
    return root;
  }
  
  public static void traverse (Node root){ // Each child of a tree is a root of its subtree.
    System.out.println(root.num);
    if (root.left != null){
        traverse (root.left);
    }
    if (root.right != null){
        traverse (root.right);
    }
}

The main concern here is identifying root node.
a) To start with, we maintain a HashMap<Integer, ordered List of Integers> to store the information already given.
2->{4,5}
1->{2,3}
3->{6}
b) Now in order to find the root,
for each of the key in the keySet
-> Find if key is present in atleast one of the value set. If yes, that is not the root.
-> There will be only one key element not present in any of the value sets, and that will be root.

A fast o(3n) solution by me.
It won't fail on LOOPS (return nulls) and won't break on multiple roots (returns the latest)

using System;
using System.Collections;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Item {
        public int value;
        public int left;
        public int right = -1;
        public bool root=true;
        public Item(int a, int b) { 
            value = a; left = b; root = true;
            Console.WriteLine("Created " + a + " - " + b);    
            }
        }
    class Node { 
        public int value;
        public Node left = null;
        public Node right = null;
        public Node(Dictionary<int, Item> h, int v)
        {
            value = v;
            Item i = Program.DirValue(h,v); if (i == null) return;
            left = new Node(h, i.left);
            if (i.right != -1) right = new Node(h,i.right);
        }
    }
    
    class Program
    {
        public static Item DirValue(Dictionary<int, Item> h, int v) {if (h.ContainsKey(v)) return h[v]; else return null;}

        static void print(Node n,string c,string s){
            Console.WriteLine(s + c+n.value);
            s = s + "           ";
            if (n.left != null) print(n.left, "L: ",s);
            if (n.right!= null) print(n.right, "R: ", s);
        }

        static Node Do(int[][] d) {
            var     h=new Dictionary<int,Item>();
            for (int i=0;i<d.Length;i++){
                Item n = Program.DirValue(h,d[i][0]);                                                 
                if (n == null) h[d[i][0]] = new Item(d[i][0], d[i][1]); else n.right = d[i][1];       
            }
            foreach (KeyValuePair<int,Item> n in h)
            {
                Item i = Program.DirValue(h, n.Value.left);                                                                  
                if (i != null) i.root = false;
                if (n.Value.right != -1) { i = Program.DirValue(h, n.Value.right);if (i != null) i.root = false;}
             }
            int root=-1;
            foreach (KeyValuePair<int, Item> n in h) if (n.Value.root) root = n.Value.value;
            if (root == -1) return null; else return new Node(h,root);
        }
        
        static void Main(string[] args)
        {
            int[][] d={ new int[]{2, 4},new int[]{1, 2},new int[]{3, 6},new int[]{1, 3},new int[]{2, 5}};
            Node r=Do(d);
            if (r!=null) print(r," ","   ");

        }
    }
}

Here is how I do it:
1. Create a hash map with node value as key and pointer to the node as value ( map<int,node*>
2. Iterate through each input pair and get the first (parent) value and check if it is already in the map. If not create a node with the value and puts its pointer in the map. Do the same for the second (child) value. Now, connect the parent to the child by pointing the left of parent to child, if left is 0. Otherwise point the right to child.

3. At this point we have the whole tree built but we don't know where it's root is. So now we need to find the root. For this, create two sets "parents" and "children". As you iterate through the input pairs, put the parent value in the parents set and child value in the children set. Finally take a parent - children set difference. The difference should have only one value which is the root node.

Here is my code:

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <queue>
#include <set>

using namespace std;

struct node{
  node* left;
  node* right;
  int value;
  node(int v){value=v;left=0;right=0;}
  bool isleaf(){return (left==0 && right==0);}
};

//Binary tree
class bin_tree{
  node* root;
public:
  explicit bin_tree(node* rootptr){
    root = rootptr;
  }
  void breadth_first(){
    breadth_first_(root);
  }
private:
  void breadth_first_(node* c_node){
      if(c_node==0)
        return;
      std::queue<node*> myqueue;
      myqueue.push(c_node);
      while(!myqueue.empty()){
          c_node = myqueue.front();
          myqueue.pop();
          std::cout<<c_node->value<<",";
          if(c_node->left!=0)
            myqueue.push(c_node->left);
          if(c_node->right!=0)
            myqueue.push(c_node->right);
      }
  }

};


void pair_to_tree_main(){

  vector<pair<int,int> > input = {make_pair(2,4),make_pair(6,2),make_pair(3,1),make_pair(6,3),make_pair(2,5)};

  //Print input
  for(size_t i=0;i<input.size();++i){
        cout<<"["<<input[i].first<<","<<input[i].second<<"], ";
  }

  map<int,node*> ptr_map;

  set<int> parents,children;

  for(size_t i=0;i<input.size();++i){
      map<int,node*>::iterator parent_itr;
      parent_itr = ptr_map.find(input[i].first);
      pair<map<int,node*>::iterator,bool> retval;
      if(parent_itr==ptr_map.end()){
          node* tmpptr = new node(input[i].first);
          retval = ptr_map.insert(make_pair(input[i].first,tmpptr));
          parent_itr = retval.first;
      }
      map<int,node*>::iterator child_itr;
      child_itr = ptr_map.find(input[i].second);
      if(child_itr==ptr_map.end()){
          node* tmpptr = new node(input[i].second);
          retval = ptr_map.insert(make_pair(input[i].second,tmpptr));
          child_itr = retval.first;
      }
      if(parent_itr->second->left==0){
          parent_itr->second->left = child_itr->second;
      }else{
          parent_itr->second->right = child_itr->second;
      }

      parents.insert(input[i].first);
      children.insert(input[i].second);

  }

  cout<<"\nParents: ";
  for(set<int>::const_iterator itr=parents.begin();itr!=parents.end();++itr){
      std::cout<<*itr<<",";
  }
  cout<<"\nChildren: ";
  for(set<int>::const_iterator itr=children.begin();itr!=children.end();++itr){
      std::cout<<*itr<<",";
  }
  //Find the root node
  int rootval;
  for(set<int>::const_iterator itr=parents.begin();itr!=parents.end();++itr){
      set<int>::iterator tmpitr = children.find(*itr);
      if(tmpitr==children.end()){
          rootval = *itr;
          break;
      }
  }
  cout<<"\nRoot node = "<<rootval;
  node* rootptr = ptr_map.find(rootval)->second;
  bin_tree mytree(rootptr);
  cout<<"\nTree bread-first:";
  mytree.breadth_first();

}

#include<iostream>
#include<vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <string>
#include <queue>
#include <sstream>
#include <iostream>
#include<string.h>
#include <iomanip>
#include <cstdio>
#include<math.h>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define ull unsigned long long
#define pi 3.141592653589793
#define graphAY_SIZE(A) sizeof(A)/sizeof(A[0])
#define PB push_back
#define INF 1<<10
using namespace std;
struct node
{
int data;
struct node*left;
struct node*right;
struct node*par;
};
map<int,struct node*>mymap;
struct node* insert(int num)
{
struct node*temp =(struct node*)malloc(sizeof(struct node));
temp->data = num;
temp->par =NULL;
temp->left = NULL;
temp->right =NULL;
return temp;
}
void join(struct node*x,struct node*y)
{
if((x)->left==NULL)
(x)->left =y;
else
(x)->right = y;
(y)->par =x;
}
struct node*get_root(struct node*z)
{
if(z->par==NULL)
return z;
else
{
return get_root(z->par);
}
}
void inorder(struct node*t)
{
if(t!=NULL)
{
inorder(t->left);
cout<<t->data<<" ";
inorder(t->right);
}
else
return;
}
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)==2)
{
if(mymap.find(a)==mymap.end())
mymap[a] = insert(a);
if(mymap.find(b)==mymap.end())
mymap[b] = insert(b);
join(mymap[a],mymap[b]);
}
struct node*t =get_root(mymap[b]);
inorder(t);
return 0;
}