calculating the sum of nodes in a single verticle line of a binary tree

C++ code\n\nint vertsum(Node* n, int cur_level, int target_level)\n{\n if (!n)\n return 0;\n\n int sum = 0;\n if (cur_level == target_level)\n sum = n->value;\n return sum + \n vertsum(n->left, cur_level-1, target_level) + \n vertsum(n->right, cur_level+1, target_level);\n}\n\n\ninvocation example:\n\nvertsum(root, 0, 1);\n\n\nEDIT:\n\nAfter clarifying the requirements, here the suggested code. Note that this is C++'ish and not exactly using Java's or C++'s standard API for lists, but you should get the idea. I assume that addNodeBefore and addNodeAfter initialize node's data (i.e. ListNode::counter)\n\nvoid vertsum(TreeNode* n, int level, ListNode& counter)\n{\n if (!n)\n return;\n\n counter.value += n->value;\n counter.index = level;\n\n if (! counter.prev)\n addNodeBefore(counter);\n vertsum(n->left, level-1, counter.prev); \n\n if (! counter.next)\n addNodeAfter(counter);\n vertsum(n->right, level+1, counter.next);\n\n return;\n}\n",

You could visit the binary tree in depth-first postorder, and use an offset to keep track of how far you moved to the left/right with respect to your starting node. Every time you move to the left, you decrement the offset, and every time you move to the right you increment the offset. If your visit procedure is called with an offset of 0, then it means that the node being visited has the same offset of your starting node (i.e. it's in the same column), and so you must add its value.\n\nPseudocode:\n\nprocedure visit (node n, int offset) {\n sumleft = 0\n sumright = 0\n if (n.left != null)\n sumleft = visit(n.left, offset - 1)\n if (n.right != null)\n sumright = visit(n.right, offset + 1)\n if (offset == 0)\n return n.value + sumleft + sumright\n else\n return sumleft + sumright;\n}\n\n\nFor example, if you call\n\nvisit(A, 0)\n\n\nyou will get the following calls:\n\nvisit(A, 0) -> E.value + F.value + A.value\n visit(B, -1) -> E.value\n visit(D, -2) -> 0\n visit(H, -3) -> 0\n visit(I, +2) -> 0\n visit(E, 0) -> E.value\n visit(C, +1) -> F.value\n visit(F, 0) -> F.value\n visit(G, +1) -> 0\n\n\nAnother example, starting from node B:\n\nvisit(B, 0)\n visit(D, -1) \n visit(H, -2)\n visit(I, 0) -> here we return I.value\n visit(E, +1)\n\n\nwhen recursion goes back to the initial call visit(B, 0) we have sumleft = I.value and sumright = 0, so we return the final result B.value + I.value, as expected.\n\nComplexity of O(n), because you visit once all nodes of your tree rooted at the starting node.\n\n\n\nAfter think about the above algorithm, I realize it has a limitation, which becomes evident when we consider a more complex tree like the following:\n\n\n\nIn this case visit(B, 0) would still return B.value + I.value, but this is not the expected result, because N is also on the same column. The following algorithm should cope with this problem:\n\nprocedure visit(node n, int c, int t) {\n sumleft = 0;\n sumright = 0;\n if (n.left != null)\n sumleft = visit(n.left, c - 1, t)\n if (n.right != null)\n sumright = visit(n.right, c + 1, t)\n if (c == t)\n return n.value + sumleft + sumright;\n else\n return sumleft + sumright;\n}\n\n\nThe idea is essentially the same, but we have now a parameter c which gives the current column, and a parameter t which is the target column. If we want the sum of the elements in the B column, then we can call visit(A, 0, -1), that is we always start our visit from node A (the root's tree), which is at column 0, and our target is column -1. We get the following:\n\n\n\nTherefore visit(A, 0, -1) = B + I + N as expected.\n\nComplexity is always O(n), where n is the number of nodes in the tree, because we visit the entire tree with depth-first postorder, and we process each node only once.\n\n\n\nIf we want to compute the sum of every column, we can use the following algorithm\n\nprocedure visit(node n, int c) {\n if (n.left != null)\n S{c} += n.value;\n visit(n.left, c - 1)\n visit(n.right, c + 1)\n}\n\n\nand call once visit(A, 0), where A is the root node. Note that S{...} in the algorithm is a map whose keys are the columns numbers (..., -2, -1, 0, 1, 2, ...) and whose values (at the end of the algorithm) are the sums of the values of nodes in that column (S{1} will be the sum of nodes in column 1). We can also use an array, instead of a map, provided that we pay attention to the indexes (arrays have no 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 (the map, or the array). If I'm not mistaken a binary tree of height h will have 2*h + 1 columns.",

What about the following? (Inside your node class, assuming getData returns the integer value, hasRight() and hasLeft() are boolean values indicating whether a right/left branch exists and getRight() and getLeft() return the next node in the right/left branch.\n\npublic int calculateVerticalLine(int numLine) {\n return calculateVerticalLineRecursive(numLine, 0);\n}\n\nprotected int calculateVerticalLineRecursive(int numLine, int curPosition) {\n int result = 0;\n if(numLine == curPosition) result += this.getData();\n if(hasRight()) result += getRight().calculateVerticalLineRecursive(numLine, curPosition+1);\n if(hasLeft()) result += getLeft().calculateVerticalLineRecursive(numLine, curPosition-1);\n return result;\n}\n",