Question 4: Implement the following function: def find_min_abs_difference(bst) T

Question

Question 4: Implement the following function: def find_min_abs_difference(bst) The function is given a binary search tree bst, where all its keys are non-negative numbers. When called, it returns the minimum absolute difference between keys of any two nodes in bst. For example, if bst is the following tree: The call find_min_abs_difference(bst) should return 1 (since the absolute difference between 6 and 7 is 1, and there are no other keys that their absolute difference is less than 1)

.Implementation requirement: The runtime of this function should be linear. That is, if bst contains n nodes, this function should run in ?(). Hint: To meet the runtime requirement, you may want to define an additional, recursive, helper function, that returns more than one value (multiple return values would be collected as a tuple).

PYTHON

Explanation / Answer

def find_min_abs_difference(bst):
    def min_abs_number(node):
        #this helper function returns (first number, second number, min_abs_difference)
        def helper(tup, root_val):
            if tup[2] is None:
                return (tup[0], root_val, abs(root_val-tup[0]))
            temp_tup = tup
            low = tup[2]
            if abs(root_val-tup[0]) < low:
                low = abs(root_val-tup[0])
                temp_tup = (left[0], root_val, low)
            if abs(root_val-tup[1]) < low:
                low = abs(root_val-tup[1])
                temp_tup = (tup[1], root_val, low)
            return temp_tup

        #handle cases of node being a leaf or one child
        if node is None:
            return None
        elif node.left is None and node.right is None:
            return (node.item.key, None, None)
        else:
            left = min_abs_number(node.left)
            right = min_abs_number(node.right)

            #if one sided, then return just return the other side.
            if left is not None:
                left_tup = helper(left, node.item.key)
            else:
                return helper(right, node.item.key)

            if right is not None:
                right_tup = helper(right, node.item.key)
            else:
                return helper(left, node.item.key)

            if left_tup[2] < right_tup[2]:
                return left_tup
            else:
                return right_tup

    answer = min_abs_number(bst.root)
return answer[2]

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.