Looping through a tree to get branch or leaf

Question

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 do tree_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 by tree_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"

Answer 1

all in all this code does what it needs to do, but czan be improved in some small points

Exception

Instead of the try-except clause, just let the exception bubble up to the caller if he passes a wrong index. returning a string in this case is almost never the correct way to treat it. Now the caller has to check each response he gets and compare it to "INPUT OUT OF RANGE". Even returning None would be better than this errorstring

list

index = list(index) is useless. tuples can be sliced too, and you can get the length of them

code

The algorithm becomes very simple. It raises a TypeError or IndexError if the caller passes in something illegal, but that's his responsibility

def tree_ref_recursion(tree, index):
    if index:
        return tree_ref_recursion(tree[index[0]], index[1:])
    else:
        return tree

The if index: just checks whether index is a non-empty tuple. There is no need to check for the type of tree. If this is no more tuple, and there is still an index, the caller passed in an illegal tree or index.

recursion

This was a recursive method. Because of the recursion, you need to check the index. You can also use a loop:

def tree_ref(tree, index):
    for idx in index:
        tree = tree[idx]
    return tree