[algogeeks] Re: Binary Tree Amazon
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 ArrayListInteger 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 ArrayListInteger findVertical(TNode root){
ArrayListInteger res = new ArrayListInteger();
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
[algogeeks] Re: Binary Tree Amazon
@all why you wants to change the tree structure do you know they don't allow that otherwise it wont be amazon question we can use Array as data Structure vertical sum in that as what jalaj told in case you wants to see working code check out \ http://shashank7s.blogspot.com/2011/02/wap-to-findout-vrtical-sum-of-nodes.html Let me know if still have any issue with problem Thanks Regards Shashank Mani The Best Way to Escape From The Problem is Solve It -- 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.
[algogeeks] Re: Binary Tree Amazon
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 ArrayListInteger 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 ArrayListInteger findVertical(TNode root){
ArrayListInteger res = new ArrayListInteger();
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
[algogeeks] Re: Binary Tree Amazon
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.
