Tree traversals python

Question

I have to define three functions: preorder(t):, postorder(t):, and inorder(t):.

Each function will take a binary tree as input and return a list. The list should then be ordered in same way the tree elements would be visited in the respective traversal (post-order, pre-order, or in-order)

I have written a code for each of them, but I keep getting an error when I call another function (flat_list()), I get an index error thrown by

if not x or len(x) < 1 or  n > len(x) or x[n] == None:
    IndexError: list index out of range

The code for my traversal methods is as follows:

def postorder(t):
    pass
    if t != None:
        postorder(t.get_left())
        postorder(t.get_right())
    print(t.get_data())

def pre_order(t):
    if t != None:
        print(t.get_data())
        pre_order(t.get_left())
        pre_order(t.get_right())

def in_order(t):
    pass
    if t != None:
        in_order(t.get_left())
        print(t.get_data())
        in_order(t.get_right())

def flat_list2(x,n):
  if not x or len(x) < 1 or  n > len(x) or x[n] == None:
    return None

   bt = BinaryTree( x[n] )
   bt.set_left( flat_list2(x, 2*n))
   bt.set_right(flat_list2(x, 2*n + 1))
 return bt

this is how i call flat_list2

flat_node_list = [None, 55, 24, 72, 8, 51, None, 78, None, None, 25]
bst = create_tree_from_flat_list2(flat_node_list,1)

    pre_order_nodes = pre_order(bst)

    in_order_nodes = in_order(bst)

    post_order_nodes = post_order(bst)

    print( pre_order_nodes)

    print( in_order_nodes)

    print( post_order_nodes)

Answer 1

First things first, I noticed that your indentation was inconsistent in the code block that you provided (fixed in revision). It is critical that you ensure that your indentation is consistent in Python or stuff will go south really quickly. Also, in the code below, I am assuming that you wanted your t.get_data() to still fall under if t != None in your postorder(t), so I have indented as such below. And lastly, I noticed that your method names did not match the spec you listed in the question, so I have updated the method names below to be compliant with your spec (no _ in the naming).

For getting the list, all you need to do is have your traversal methods return a list, and then extend your list at each level of the traversal with the other traversed values. This is done in lieu of printing the data.

def postorder(t):
    lst = []
    if t != None:
        lst.extend(postorder(t.get_left()))
        lst.extend(postorder(t.get_right()))
        lst.append(t.get_data())
    return lst

def preorder(t):
    lst = []
    if t != None:
        lst.append(t.get_data())
        lst.extend(preorder(t.get_left()))
        lst.extend(preorder(t.get_right()))
    return lst

def inorder(t):
    lst = []
    if t != None:
        lst.extend(inorder(t.get_left()))
        lst.append(t.get_data())
        lst.extend(inorder(t.get_right()))
    return lst

This will traverse to the full depths both left and right on each node and, depending on if it's preorder, postorder, or inorder, will append all the traversed elements in the order that they were traversed. Once this has occurred, it will return the properly ordered list to the next level up to get appended to its list. This will recurse until you get back to the root level.

Now, the IndexError coming from your flat_list, is probably being caused by trying to access x[n] when n could be equal to len(x). Remember that lists/arrays in Python are indexed from 0, meaning that the last element of the list would be x[n-1], not x[n].

So, to fix that, replace x[n] with x[n-1]. Like so:

def flat_list2(x,n):
    if not x or len(x) < 1 or n < 1 or n > len(x) or x[n-1] == None:
        return None

    bt = BinaryTree( x[n-1] )
    bt.set_left( flat_list2(x, 2*n))
    bt.set_right(flat_list2(x, 2*n + 1))
    return bt

Answer 2

You should actually write three function that return iterators. Let the caller decide whether a list is needed. This is most easily done with generator functions. In 3.4+, 'yield from` can by used instead of a for loop.

def in_order(t):
    if t != None:
        yield from in_order(t.get_left())
        yield t.get_data()
        yield from in_order(t.get_right())

Move the yield statement for the other two versions.