Finding the heaviest path in a binary tree efficiently - python

Question

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?

Given the class:

    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) + "]"     

I calculate the weight of the heaviest path:

def weight(node):
    if node == None:
        return 0
    if weight(node.left)>weight(node.right):
        return node.val+weight(node.left)
    else:
        return node.val+weight(node.right)

And then I try to return the heaviest path as a list:

def heavy_path(node):
    if node==None:
        return []
    elif node.val+weight(node.left)> 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

So that given a tree like [[None a 7 None] b 5 [[None c 8 None] d 3 None]]:

>>> weight(t)
16
>>> heavy_path(t)
[5, 3, 8]

What would be a better way of doing this?

Answer 1

Assuming that you are interpreting the heaviest path as being a path that always begins with the root of the tree and descends down to a single leaf. You could try merging the weight-finding and path-building operations:

def heavy_path(node):
  if not node
    return (0,[])
  [lweight,llist] = heavy_path(node.left)
  [rweight,rlist] = heavy_path(node.right)
  if lweight>rweight:
    return (node.val+lweight,[node.val]+llist)
  else:
    return (node.val+rweight,[node.val]+rlist)

Or using a time-honoured technique to speed up this kind of calculation through Memoization. Once you've used memoization once, you could just keep the pathweight values up to date as you alter your tree.

def weight(node):
  if node == None:
      return 0
  node.pathweight=node.val+max(weight(node.left),weight(node.right))
  return node.pathweight

def heavy_edge(node):
  if not node.left:
    lweight=0
  else:
    lweight=node.left.pathweight
  if not node.right:
    rweight=0
  else:
    rweight=node.right.pathweight
  if lweight>rweight:
    return [node.val,heavy_edge(node.left)]
  else:
    return [node.val,heavy_edge(node.right)]

weight(t) #Precalculate the pathweight of all the nodes in O(n) time
heavy_edge(T) #Use the precalculated pathweights to efficient find list the heaviest path in O(lg n) time