2
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ @MathiasEttinger, for sure, posted the question to make it more self contained. \$\endgroup\$ – Lin Ma Dec 30 '16 at 23:08
  • 1
    \$\begingroup\$ (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. \$\endgroup\$ – greybeard Dec 31 '16 at 8:07
  • 3
    \$\begingroup\$ I am wondering if there is a way to not write recursive code With a data structure defined and represented recursively: Why? \$\endgroup\$ – greybeard Dec 31 '16 at 8:11
  • \$\begingroup\$ @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? \$\endgroup\$ – Lin Ma Jan 12 '17 at 0:10
  • \$\begingroup\$ @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. \$\endgroup\$ – Lin Ma Jan 12 '17 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.