calculating the sum of nodes in a single verticle line of a binary tree
-
11-11-2019 - |
Question
For a binary tree i want to get the sum of all nodes that fall in a single verticle line. I want the sum of nodes in each verticle node
A
/ \
B C
/ \ / \
D E F G
/ \
H I
IF you look at above tee
line 0 A E F so sum = A+E+F
line -1 B I so sum = B +I
line 1 C so sum = C
line 2 G so sum = G
I implemented following algorithm
Map<Integer,Integere> mp = new HashMap<Integer,Integer>()
calculate(root,0);
void calculate(Node node, int pos){
if(node==null)
return ;
if(mp.containsKey(pos) ){
int val = mp.get(pos) + node.data;
mp.put(pos,val);
}
else{
mp.put(pos,node.data);
}
calculate(node.left,pos-1);
calculate(node.right,pos+1);
}
- I think the above algo is fine.Can any one confirm?
- Also how can i do it without using HashMap,arraylist or any such collection datatype of java.One method is two is 2 arrays one for storing negative indexes(mapped to positive) and one for positive indexs(right side of root).But we dont know what the size of array will be.
- One approach is to use doubly link list and add a node on right/left movement if necessary. Am not getting how can i implement this approach? Any other simple/more time efficient approach?
- Is the complexity of the above code i imolmeted is O(n)? (am not good at analysing time complexity , so asking )
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow