Tree

     In week six, we have been introduced a new type of data structure which is called Tree and our lecture is mainly focus on Binary Tree. Binary Tree is a tree-like data structure which has a root and at most two children. It contains some internal nodes as well,whose number also has to be less and equal to two.The overview of Binary Tree is like this

2 is the root of this Binary tree. 7, 5, 6, 9 are internal nodes and 2, 5, 11, 4 are children.

      Moreover, we have been introduced 3 different types of traversal, pre-order traversal, in-order traversal and post-order traversal. For pre-order traversal, root will be visited first then the left subtree finally the right subtree. In-order traversal is left subtree first, root second and right subtree at last. Post-order is left(first)and right(second) tree will be visited respectively and root is the last one to be visit. 

      Understand this three traversals graphically is easy but when I try to write it as codes, it becomes hard for me.But the slides of week six help me a lot.At least I understand how to implement codes for those three traversals using recursion. Honestly, the concept is really easy. If the input is None, we have to return None.Else we have to use recursion.

     Take a pre-order traversal as an example, since we have to visit root first so if the input is not None, we have to return t[0] first which  represent the root then we return t[1] afterwards as it represents the left of the subtree and finally t[2] which represent the right tree. Because there may have more internal nodes in both left and right subtree and each internal nodes with its children or other internal nodes can be seen as another new binary tree so the t[1] and t[2] can be nested lists, which requires us using recursion. And that is the point of implementing traversals' codes.