title: Finding the heaviest path in a binary tree efficiently - python
body: <p>I am trying to solve the following: finding the weight of the heaviest node in the tree and also representing that node as a list. This is what I came up with, but I am pretty sure that it is a very messy solution. Any advice on doing it more efficiently within the frame of the class given?</p>
  
  <p>Given the class:</p>
  
  <pre><code>    class Tree_node():
          def __init__(self,key,val):
              self.key=key
              self.val=val
              self.left=None
              self.right=None  
  
      def __repr__(self):
      return "[" + str(self.left) + " " + str(self.key) + " " + \
                  str(self.val) + " " + str(self.right) + "]"     
  </code></pre>
  
  <p>I calculate the weight of the heaviest path:</p>
  
  <pre><code>def weight(node):
      if node == None:
          return 0
      if weight(node.left)&gt;weight(node.right):
          return node.val+weight(node.left)
      else:
          return node.val+weight(node.right)
  </code></pre>
  
  <p>And then I try to return the heaviest path as a list:</p>
  
  <pre><code>def heavy_path(node):
      if node==None:
          return []
      elif node.val+weight(node.left)&gt; node.val+weight(node.right):
          return [node.val] + filter_values(path_values(node.left))
      else:return [node.val] + filter_values(path_values(node.right))
  
  def path_values(node):
      if node == None:
          return 0
      return [node.val,path_values(node.left),path_values(node.right)]
  
  def filter_values (node):
      values = []
      sub_lists = []
      if node != 0:
          for value in node:
              if isinstance(value, list):
                  sub_lists = filter_values(value)
              else:
                  if value != 0:
                      values.append(value)
      return values+sub_lists
  </code></pre>
  
  <p>So that given a tree like [[None a 7 None] b 5 [[None c 8 None] d 3 None]]:</p>
  
  <pre><code>&gt;&gt;&gt; weight(t)
  16
  &gt;&gt;&gt; heavy_path(t)
  [5, 3, 8]
  </code></pre>
  
  <p>What would be a better way of doing this?</p>