Michael T Michael T - 2 years ago 187
Python Question

Calculate the max difference between nodes in a binary tree

Is there a way to calculate the max difference between node values without storing in a list? I was hoping to do it in 1 pass, but it doesn't seem possible. This was from a codility interview question to calculate the amplitude of the binary tree defined as the max absolute difference of the nodes.

def max_diff(nodes):
return abs(max(nodes) - min(nodes))

def amplitude(T):
nodes = []
def calc_amplitude(T, nodes):

if not isinstance(T, tuple):
if not isinstance(T, int):
return 0
return T
[calc_amplitude(t, nodes) for t in T]
return max_diff(nodes)
return calc_amplitude(T, nodes)

tree = (5, (8, (12, None, None), (2, None, None)),(9, (7, (1, None, None), None), (4, (3, None, None), None)))

print amplitude(tree)

Answer Source

In case that you want to know the maximum difference between two nodes on any path from root to leaf you can use following code:

def amplitude(tree, cur_min=None, cur_max=None):
    if tree is None:
        if cur_min is None:
            return 0
            return cur_max - cur_min

    if cur_min is None:
        cur_min = cur_max = tree[0]
        cur_min = min(cur_min, tree[0])
        cur_max = max(cur_max, tree[0])

    return max(amplitude(tree[1], cur_min, cur_max),
               amplitude(tree[2], cur_min, cur_max))

It will track minimum and maximum value on each path. Once it reaches the leaf it will simply return the difference between those two thus stopping the recursion. For non-leaf nodes it will first update minimum and maximum value. Then it recurses to both children and returns the maximum value between the two results.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download