Week6 - Binary Tree ADT

Hey Everyone,

This week we learned a new kind of ADT -- Tree. By learning this ADT, I am more and more familiar with creating a class to represent a type. This Tree ADT leads to a new way of thinking problems. Like Stacks ADT, add to top & move from top; Tree ADT is also well-represented by its name. Tree has branches(subtree), leafs(node with no children) etc. A common kind of tree is a binary tree which contains at most two subtrees.

In this post, I am going to clarify several terminology that bothered me in past few weeks, then I will introduce a implicit recursion, finally I will talk about an important logic to write recursion function from binary Tree type object (simultaneously showing how to traversal a tree).

1. Module vs Class; Method vs Function

When we are implementing class Tree this week, we not only create class method but also outside class, in module functions.
Module is a collection of functions, variables grouped together n a file. Class  is another kind of object that is similar to module, it contains functions and variables. More important, a class is how Python represents a type.
A method is another kind of function that is attached to a particular type. Therefore, only the functions inside a class can be called methods of that particular class.

In particular, __contains__(self: 'Tree', value: object) is method. arity(t: Tree) is a function.
Note another difference in type contract, in method 'Tree' has quotation mark with it whereas in function Tree has no quotation marks. In my opinion, this is because when a method is defined in a class, its first parameter must be variable that represents the object the method is being called on (by convention this called self). This quotation mark is used to separate this particular parameter with others.
Any comment will be appreciated :))

2. __repr__ method

This function shows how to use implicit recursion in a function, which means the exactly function name does not appear in the function but it also calls itself. This is very common when we create class method by modifying special methods.

def __repr__(self: 'Tree') -> str:

      """Return representation of Tree as a string"""

      return ('Tree(' + repr(self.value) + ', ' +

              repr(self.children) + ')')

3. Traversal a tree

We also learned how to "climb a tree" in different orders, that is what traversal a tree means. The most important thing I learned from this part is to use left tree and right tree to a separate a Tree and recurse a Tree. Instead of just recursing a method within Tree class, I guess this new logic is will be very useful in future studies.

There are three typical traversal: preorder, inorder and postorder.

Preorder: visit root first, then preorder left tree, finally preorder right

Inorder: visit inorder left tree first, then root, finally inorder right

Postorder: visit postorder left tree first, then right tree, finally root

I will provide the Preorder Traversal here since other two uses exactly same logic and their codes are very similar to this one.

def preorder(tl: 'TreeList') -> list:

    """

    Return list of values in tl in preorder

    >>> preorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])

    [5, 4, 3, 2, 1]

    """

    return [] if tl is None else ([tl[0]] + preorder(tl[1]) + preorder(tl[2]))

This is the first week we see the Tree ADT, I may add more thinking in future posts, if there is some~

We're going to have our 1st term test next week, GOOD LUCK TO EVERYONE!