Use dynamic programming to find the shortest path through nodes in a binary lattice structure

cheapest_path.py

"""
Figure out the smallest sum for a binary lattice
of nodes where children are shared.

e.g.

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

The solution should run in O(n) time
"""


class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    

def create_lattice():
    _51 = Node(4)
    _52 = Node(7)
    _53 = Node(6)
    _54 = Node(9)
    _55 = Node(8)
    _41 = Node(5, left=_51, right=_52)
    _42 = Node(3, left=_52, right=_53)
    _43 = Node(9, left=_53, right=_54)
    _44 = Node(6, left=_54, right=_55)
    _31 = Node(8, left=_41, right=_42)
    _32 = Node(7, left=_42, right=_43)
    _33 = Node(2, left=_43, right=_44)
    _21 = Node(4, left=_31, right=_32)
    _22 = Node(5, left=_32, right=_33)
    return Node(1, left=_21, right=_22)
    

def find_sum_of_cheapest_path(root):
    def update_cheapest(node):
        if node.left is not None:
            if not hasattr(node.left, 'cheapest'):
                update_cheapest(node.left)
                if node.right is None:
                    node.cheapest = node.left.cheapest
                    return
        if node.right is not None:
            if not hasattr(node.right, 'cheapest'):
                update_cheapest(node.right)
                if node.left is None:
                    node.cheapest = node.right.cheapest
                    return
        if node.left is None and node.right is None:
            node.cheapest = node.val
        else:
            node.cheapest = node.val + min(node.left.cheapest,
                                           node.right.cheapest)
    update_cheapest(root)
    return root.cheapest


def main():
    print find_sum_of_cheapest_path(create_lattice())

if __name__ == '__main__':
    main()