More Binary Trees

Today in the lab we worked on an interesting new approach to binary trees. Rather than using a separate class for each node in the tree we kept track of every item using the built-in Python list class. There's one condition with using this technique and that is the tree must be fully complete, the items fill up the levels one by one from left to right. For example if your tree contained these items [1, 2, 3, 4, 5, 6] the tree would always look like this:

But it could never look like this:

Every level must be filled left to right no matter what. This implementation is interesting because the only information you have about each node is it's index in the list. This means that in order to find its parent or child nodes you need a formula that takes the nodes index and outputs the index of the parent/child. I was able to find this formula by writing out the the first 4 or 5 cases and looking for a pattern. For example, the index of the left child 'j' of a node at index 'i':

 i      j 

0 -> 1

1 -> 3

2 -> 5

3 -> 7

Then using this data I tried to find a pattern. In this case j = (2*i)+1, so the index of every left child of a node at index 'i' is equal to (2*i)+1. After finding the patterns for navigating the index's for parent and child nodes you could put them into methods and basically use the same techniques for solving inorder, max_sum, etc.