Entry #3: True CS Students Stay Awake at 2AM Drawing Tree Traversals

In light of E3A and a slight 2 A.M. recursion headache I am going to put a short sweet post about the different tree traversals. This is to serve as an organised reference, a stark contrast to the state of my room.

Def: Tree Traversal

• the process of visiting/examining/updating each node in a tree data structure
• there are multiple ways to traverse a tree

1.  Pre-Order:
    
         root -> left subtree -> right subtree
    def preorder

Things to Note:

• Start from the top and go down
• You hit everything in your path
• Go all the way down the left and then you can start on the ones on the right that you didn't get

Analogy: kind of like when you're getting your 8 gym badges, very linear, you go forward not back

Code:
def preorder(tl: 'TreeList') -> list:
     return [] if tl is None else ([tl[0]]\
               + preorder(tl[1]) + preorder(tl[2]))












2. In-Order:

       left subtree -> root -> right subtree

    Things to Note:

• Start at the bottom most left
• Always visit "root" after the left child but before you go to the right child 
• If there is no left child go straight to root

Analogy: The left is a cave (zubats...), the root is a healing centre, and the right is a field



Code:
def inorder(tl: 'TreeList') -> list:
    return [] if tl is None else inorder(tl[1])\
                                + [tl[0]] + inorder(tl[2])








3. Post-Order:

 left subtree -> right subtree -> root

Things to Note:

•  Start at the most left
• The main root will be your last hit

Analogy: Those "puzzles" where you have to take out all the underlings, starting from weakest to strongest, until you get to the final boss. (left side is weaker than right side cause right handed)

Code:
 def postorder(tl: 'TreeList') -> list:
    return [] if tl is None else postorder(tl[1])\                         + postorder(tl[2]) + [tl[0]]







 And that concludes 2 AM blogging and the plethora of bad Pokemon analogies.