CareerCup

It doesn't matter.It isn't a binary search tree.

HashMap<Integer, BNode> map = new HashMap<Integer, Node>();
BNode p, c;
for (int i = 0; i < a.length; i++) {
if (!map.containsKey(a[i]))
p = new BNode(a[i]);
else
p = map.get(a[i]);
if (!map.containsKey(i))
c = new BNode(i);
else
c = map.get(a[i]);

if (p.left == null)
p.left = c;
else
p.right = c;
c.parent = p;
map.put(a[i], p);
map.put(i, c); //here may use clone()???
}

and add the case of root at the beginning of for loop, like assuming a[i]=-1 => i is the root. may record this node and return it at the end of the method

If such array is given How to decide whether 'c' is a left child or right child of 'p'?

@aditya..
m also having d same doubt..
may b we cn take any order..

if it doesn't matter then
FOR FIRST case:
make two arrays
c1 and c2 and initialize elements with null;

for( i = 0 to numelments )
if( a[c] ){
if( c1[p]!=null) c1[p]=c
else if(c2[p]!=null) c2[p]=c;
}
}

search for p suct that a[p] is not defined
choose this node as root.
Now you have child information at hand for each node Simply we can apply DFS
OR BFS to make the tree while traversing.

I think all you need to do is to walk through the array and create two nodes - one for child and one for parent. Of course you check first if the elements already exist. Create a hash table to quickly check the existence of the elements. Once you have pointers to parent and child nodes, simply associate left or right child based on the value i > a[i].

1. Hash values in hash table, chain in increasing order of index i.e. a[i]=p, a[j]=p hash is done as Hash[p]--> i---> j such that i < j
2. make root
3. root->left= Hash[root->data]-->first element in chain (i)
4. root->right=Hash[root->data]--->second element in chain (j)
5. repeat