class Node:
    def __init__(self, k, l=None, r=None):
        self.k = k
        self.l = l
        self.r = r


def max_diff(node):
    return max_diff_recur(node, -1, -1)

def max_diff_recur(node, max_seen, max_diff):

    if node == None: return max_diff

    curr = node.k
    if curr < max_seen:
        diff = max_seen - curr
        max_diff = max(max_diff, diff)
    elif curr > max_seen:
        max_seen = max(max_seen, curr)

    l = max_diff_recur(node.l, max_seen, max_diff)
    r = max_diff_recur(node.r, max_seen, max_diff)

    return max(l, r)


if __name__ == "__main__":
    n1 = Node(1)
    n4 = Node(4)
    n7 = Node(7)
    n13 = Node(13)
    n6 = Node(6, n4, n7)
    n14 = Node(14, n13)
    n3 = Node(3, n1, n6)
    n10 = Node(14, n14)
    n8 = Node(8, n3, n10)
    print(max_diff(n8))