Question 2 in HW assignment 5 had a "find closest key" method (binary tree).
I got all the points for it but I feel that there must be a shorter way (code wise) to implement the solution. The main problem is that in our version of the binary tree class there is no way to access the parent node. In order to find the closest key one must keep in mind that once we do reach the bottom of the tree to the supposed closest leaf the number on whom we are implementing the method may be a successor or a predecessor of a closer node up the tree (rather than the leaf on the bottom). We cant travel back up to check that, therefore that entails using very hefty extra code (in an envelope recursion) to keep in mind the node our current position is a predecessor or a successor of.
I was wondering if the course staff or anyone else has a relatively short correct implementation of this method..Or, does the way this class is built in this case mean that the only way is in fact to use an envelope recursion (not talking about a short one) and keep the closest key along the way in order to compare it to that final leaf.
Date: 08 Aug 2015 19:12
Number of posts: 2
RSS: New posts
Here's a possible solution, without the need to go upwards in the tree:
def find_closest_key(node, k): if node==None: return None if node.key == k: return node.key min_diff = abs(node.key - k) min_key = node.key if node.key > k: key = find_closest_key(node.left, k) else: key = find_closest_key(node.right, k) if key != None and abs(key - k) < min_diff: min_key = key return min_key