# Vertical sum in a given binary tree

I'm working on this problem,

Problem statement,

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.

Examples:

     1
/   \
2      3
/ \    / \
4   5  6   7


The tree has 5 vertical lines

• Vertical-Line-1 has only one node 4 => vertical sum is 4
• Vertical-Line-2: has only one node 2=> vertical sum is 2
• Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
• Vertical-Line-4: has only one node 3 => vertical sum is 3
• Vertical-Line-5: has only one node 7 => vertical sum is 7

So expected output is 4, 2, 12, 3 and 7

I’m wondering if there is a way to not write recursive code:

from collections import defaultdict
class TreeNode:
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right
def vertical_traverse(self, level):
stack = []
result = defaultdict(list) # key: level, value: list of node identifier
stack.append((self,level))
while len(stack) > 0:
node, level = stack.pop(-1)
result[level].append(node.value)
if node.left:
stack.append((node.left, level-1))
if node.right:
stack.append((node.right, level+1))
return result

if __name__ == "__main__":
root = TreeNode(1, TreeNode(2, TreeNode(4, None, None), TreeNode(5, None, None)), TreeNode(3, TreeNode(6, None, None), TreeNode(7, None, None)))
result = root.vertical_traverse(0)
for k,v in result.items():
print k, sum(v)

• @MathiasEttinger, for sure, posted the question to make it more self contained. – Lin Ma Dec 30 '16 at 23:08
• (posted the question please use a block quote to make parts stand out that are "not your own" (attribution by providing a link is sufficient in my book)) So, the nodes of a vertical line have the same difference between left and right links followed to get from the root to each node. – greybeard Dec 31 '16 at 8:07
• I am wondering if there is a way to not write recursive code With a data structure defined and represented recursively: Why? – greybeard Dec 31 '16 at 8:11
• @greybeard, for the purpose of trying to see if writing in iterative way is faster than recursive way. For your comments, With a data structure defined and represented recursively, I do not quite get it, what data structure do you mean -- TreeNode? – Lin Ma Jan 12 '17 at 0:10
• @greybeard, for your comments --  please use a block quote to make parts stand out that are "not your own" , the complete non-recursive version of code is my own. I post an external link since I want to show how other people is doing recursive way for the problem. if you have any thoughts on my original question, it will be great. – Lin Ma Jan 12 '17 at 0:12