My implementation tries to create a doubly linked list, each node of
which will hold the value of sum of all nodes in a particular
vertical.If there is no requirement for the final output to state
vertical number against the sum (and indeed there is no such
requirement in the question ), then my approach to show the final
vertical sums will be to first traverse left till list->prev is not
null thereby reaching the left end of the doubly linked list and then
traverse from left end to right end (till list->next !=NULL) printing
the list->data which will store the sums.
dList * GetVerticalSum(node * tree, dList * list)
{
if(tree == NULL) return NULL;
if(list == NULL )
list = getdNode(); //list->prev and list->next are set to NULL
and
list->data to 0 by getdNode()
list->data += tree->data;
if(tree->left !=NULL)
{
if(list->next == NULL)
{ list->prev = getdNode();
list->prev->next = list;
}
GetVerticalSum(tree->left, list->prev);
}
if(tree->right != NULL)
{
if(list->next == NULL)
{
list->next = getdNode();
list->next->prev = list;
}
GetVerticalSum(tree->right, list->next);
}
return list;
}
On Feb 16, 11:44 am, Jammy <xujiayiy...@gmail.com> wrote:
> 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.
