This is my solution to a problem from MIT's 6.034 Artificial Intelligence course (see the heading Tree reference on 6.034 Artificial Intelligence, Lab 0). Can you please help me improve my solution (keep in mind I am a beginner with no formal education in Computer Science)? To be clear, I am NOT taking this for school credit, this is an old class from 2010 available through MIT OpenCourseWare. SOURCE
Your job is to write a procedure that is analogous to list referencing, but for trees. This "tree_ref" procedure will take a tree and an index, and return the part of the tree (a leaf or a subtree) at that index. For trees, indices will have to be lists of integers. Consider the tree in Figure 1, represented by this Python tuple:
(((1, 2), 3), (4, (5, 6)), 7, (8, 9, 10))
To select the element 9 out of it, we’d normally need to do something like
tree[3][1]
. Instead, we’d prefer to dotree_ref(tree, (3, 1))
(note that we’re using zero-based indexing, as in list-ref, and that the indices come in top-down order; so an index of (3, 1) means you should take the fourth branch of the main tree, and then the second branch of that subtree). As another example, the element 6 could be selected bytree_ref(tree, (1, 1, 1))
.Note that it’s okay for the result to be a subtree, rather than a leaf. So
tree_ref(tree, (0,))
should return((1, 2), 3)
.
My Solution:
def tree_ref(tree, index):
try:
index = list(index)
if not isinstance(tree, tuple) or len(index) == 0:
return tree
else:
return tree_ref(tree[index[0]], index[1:])
except IndexError:
return "INPUT OUT OF RANGE"