Calculation of the sum of nodes in one vertical line of a binary tree

Question

For a binary tree, I want to get the sum of all the nodes that fall on the same line with a vertical line. I need the sum of nodes at each node node

A / \ BC / \ / \ DEFG / \ HI 

IF you look above tee

 line 0 AEF so sum = A+E+F line -1 BI so sum = B +I line 1 C so sum = C line 2 G so sum = G 

I implemented the 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 algorithm is ok. does anyone confirm?
• Also, how can I do this without using a HashMap, arraylist, or any such data type of the java.One collection method — two arrays, one for storing negative indices (mapped to positive) and one for positive indices (to the right of the root). But we do not know what the size of the array will be.
• One approach is to use a double link list and add a node to the right / left if necessary. I'm not how can I implement this approach? Any other simple / longer time efficient approach?
• Is the complexity of the above code i imolmeted is O (n)? (I'm not very good at analyzing time complexity, so asking)

Answer 1

C ++ code

 int vertsum(Node* n, int cur_level, int target_level) { if (!n) return 0; int sum = 0; if (cur_level == target_level) sum = n->value; return sum + vertsum(n->left, cur_level-1, target_level) + vertsum(n->right, cur_level+1, target_level); } 

Call example:

 vertsum(root, 0, 1); 

EDIT:

After clarifying the requirements, a code is proposed here. Note that this is C ++ 'ish and does not exactly use the standard Java or C ++ API for lists, but you should get this idea. I assume that addNodeBefore and addNodeAfter initialize node data (i.e. ListNode::counter )

 void vertsum(TreeNode* n, int level, ListNode& counter) { if (!n) return; counter.value += n->value; counter.index = level; if (! counter.prev) addNodeBefore(counter); vertsum(n->left, level-1, counter.prev); if (! counter.next) addNodeAfter(counter); vertsum(n->right, level+1, counter.next); return; } 

Answer 2

You can visit the binary tree in depth post-processing and use the offset to track how far you have moved left / right in relation to your start node. Each time you move left, you decrease the offset, and each time you move right, you increase the offset. If your visit procedure is called with an offset of 0 , then this means that the visited node has the same offset of your starting node (that is, in the same column), and therefore you must add its value.

pseudo code:

 procedure visit (node n, int offset) { sumleft = 0 sumright = 0 if (n.left != null) sumleft = visit(n.left, offset - 1) if (n.right != null) sumright = visit(n.right, offset + 1) if (offset == 0) return n.value + sumleft + sumright else return sumleft + sumright; } 

For example, if you call

 visit(A, 0) 

You will receive the following calls:

 visit(A, 0) -> E.value + F.value + A.value visit(B, -1) -> E.value visit(D, -2) -> 0 visit(H, -3) -> 0 visit(I, +2) -> 0 visit(E, 0) -> E.value visit(C, +1) -> F.value visit(F, 0) -> F.value visit(G, +1) -> 0 

Another example starting with node B :

 visit(B, 0) visit(D, -1) visit(H, -2) visit(I, 0) -> here we return I.value visit(E, +1) 

when the recursion returns to the initial call to visit(B, 0) , we have sumleft = I.value and sumright = 0 , so we return the final result B.value + I.value , as expected.

The complexity is O (n), since you visit once all the nodes of your tree embedded at the beginning of the node.

---

After thinking about this algorithm, I understand that it has a limitation, which becomes obvious if we consider a more complex tree, similar to the following:

In this case, visit(B, 0) will still return B.value + I.value , but this is not the expected result, because N also in the same column. The following algorithm should handle this problem:

 procedure visit(node n, int c, int t) { sumleft = 0; sumright = 0; if (n.left != null) sumleft = visit(n.left, c - 1, t) if (n.right != null) sumright = visit(n.right, c + 1, t) if (c == t) return n.value + sumleft + sumright; else return sumleft + sumright; } 

The idea is essentially the same, but now we have parameter c , which gives the current column, and parameter t , which is the target column. If we want to get the sum of the elements in column B , then we can call visit(A, 0, -1) , that is, we always start our visit from node A (the root tree), which is in column 0, and our goal is the column -one. We get the following:

Therefore, visit(A, 0, -1) = B + I + N , as expected.

The complexity is always O (n), where n is the number of nodes in the tree, because we visit the entire tree with depth imaging and process each node only once.

---

If we want to calculate the sum of each column, we can use the following algorithm

 procedure visit(node n, int c) { if (n.left != null) S{c} += n.value; visit(n.left, c - 1) visit(n.right, c + 1) } 

and call visit(A, 0) once, where A is the root of the node. Note that S{...} in the algorithm is a mapping whose keys are the column numbers (..., -2, -1, 0, 1, 2, ...) and the values ​​(at the end of the algorithm) are the sum of the nodes in this column ( S{1} will be the sum of the nodes in column 1). We can also use an array instead of a map, provided that we pay attention to indexes (arrays do not have negative indexes). The algorithm is still O (n) because we traverse the entire tree only once. However, in this case, we need additional space to store the sum for all columns (map or array). If I am not mistaken, a binary tree with height h will have columns 2*h + 1 .

Answer 3

What about the next one? (Inside the node class, if getData returns an integer value, hasRight () and hasLeft () are boolean values ​​indicating whether the right / left branch exists and getRight () and getLeft () return the next node to the right / left branch.

 public int calculateVerticalLine(int numLine) { return calculateVerticalLineRecursive(numLine, 0); } protected int calculateVerticalLineRecursive(int numLine, int curPosition) { int result = 0; if(numLine == curPosition) result += this.getData(); if(hasRight()) result += getRight().calculateVerticalLineRecursive(numLine, curPosition+1); if(hasLeft()) result += getLeft().calculateVerticalLineRecursive(numLine, curPosition-1); return result; }