hash would be a perfect choice. I make a MinMaxHash class which would keep track of the min and max value of the key.(since in this case we would never remove a key, thus this primitive approach works. Otherwise use treeMap)
class MinMaxHash extends HashMap{ private Integer min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; @Override public Object put(Object key, Object value){ if((Integer)key < min){ min = (Integer)key; } if((Integer)key > max){ max = (Integer)key; } return super.put(key,value); } public Integer getMin(){return min;} public Integer getMax(){return max;} } The propagate(TNode t, int k, MinMaxHash res) would form a MinMaxHash-- >res. public static void propagate(TNode t, int k, MinMaxHash res){ if(t == null){ return; }else{ if(res.containsKey(k)){ res.put(k,(Integer)res.get(k)+t.data); }else{ res.put(k, new Integer(t.data)); } propagate(t.left,k-1,res); propagate(t.right,k+1,res); } } The ArrayList<Integer> findVertical(TNode root) would return a ArrayList containing the result. The idea is to form a MinMaxHash for left subtree and right subtree. And test a few cases for the root and the line number for the right subtree. The code should be pretty self-explanatory. (TNode has int data, TNode left and TNode right)....excuse me for the poor writings of java code, I suck at writing beautiful java code like others in this group do.. public static ArrayList<Integer> findVertical(TNode root){ ArrayList<Integer> res = new ArrayList<Integer>(); MinMaxHash left = new MinMaxHash(); MinMaxHash right = new MinMaxHash(); propagate(root.left,0,left); propagate(root.right,0,right); if(left.size()>0){ for(int i = left.getMin(); i <= left.getMax(); i++){ res.add((Integer)left.get(i)); } } if(left.getMax()==0 || left.size() ==0){ res.add(root.data); }else{ res.set(res.size()-1, (Integer)res.get(res.size()-1)+root.data); } if(right.size()>0){ int start = right.getMin(); if(start < 0){ res.set(res.size()-1,(Integer)res.get(res.size()-1)+ (Integer)right.get(start)); start++; } for(int i = start; i <= right.getMax(); i++){ res.add((Integer)right.get(i)); } } return res; } On Feb 14, 9:11 am, sankalp srivastava <richi.sankalp1...@gmail.com> wrote: > Just a slight addition , you would also like to keep a record for the > maximum range of the levels (assuming the function is called as > (root , 0)) > > On Feb 14, 5:25 pm, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > > > > > > > > > use hash > > > take an array verticalsum[]={0}; > > > the function will be like this > > void vertcal_sum(node *root, int level){ > > if(root!=NULL){ > > verticalsum[level]+=root->data; > > vertcal_sum(root->left,level-1); > > vertcal_sum(root->left,level+1); > > } > > > } > > On Mon, Feb 14, 2011 at 5:04 PM, bittu <shashank7andr...@gmail.com> wrote: > > > Given a binary tree with no size limitation, write a program to find > > > the sum of each vertical level and store the result in an appropriate > > > data structure (Note: You cannot use an array as the tree can be of > > > any size). > > > > 4 > > > / \ > > > 7 8 > > > / \ / \ > > > 10 11 / 13 > > > 12 > > > > here 4(root) , 11(leftsubtree's right child ), 12 (rightsubtree's left > > > child) are in same vertical Line > > > > so here vertical line 1 is fro 10 > > > vertical line 2 sum is 7 > > > > vertical line 3 sum is 4+11+12=27 (May Have Some Doubt So i Have > > > represented the figure in correct way) > > > > vertical line 4 is 8 > > > vertical line 5 is 13 > > > > Hope its clear to every one > > > > Thanks & Regards > > > Shashank Mani > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > With Regards, > > *Jalaj Jaiswal* (+919019947895) > > Software developer, Cisco Systems > > B.Tech IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.