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 <[email protected]>
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 <[email protected]> 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 <[email protected]> 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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
