Blog Entry #3: Binary Tree

Blog Entry #3: Binary Tree    

Oct 17th

    This week we learned about Binary Tree and its related data storing methods, such as pre-order traversal, in-order traversal, and post-order traversal.  A binary tree is made of nodes, where each node contains a "left" children and a "right" children.  Personally, I think binary tree is an important tool in programming because this type of data structure are often used to organize ordered elements，e.g. "ordered binary tree"，a > b > c . When you insert an item,  all you need is to compare the item with the root,  if the item is smaller to the root then proceed with same comparison with the left subtree recursively, or the right subtree if the item is greater. That's why binary tree can be so useful to solve binary search problems.

    The in-class exercises on pre-order, in-order, post-order traversals again require the  recursive way of thinking. Any given tree is made of 3 elements, the root, left subtree, and the right subtree. The root is a value, and the subtrees are either empty or represent values that are also the parent nodes for its children. And this pattern forms a TreeList:

"""     
        A TreeList is a Python list with 3 elements        
       --- element 0 is a value      
       --- element 1 is either a TreeList or None 
        --- element 2 is either a TreeList or None
"""


     When I was working on the exercise e4a,  I applied my understanding of the structure of the binary tree and solve this problem by using simple recursive strategy:

"""

       return [root,   make_tree(preorder[1: root_index + 1], inorder[:root_index]),  make_tree(preorder[(root_index + 1):],inorder[root_index + 1:])]

"""

    Because in pre-order,  the path goes from root,  left subtree, and right subtree. And in in-order, the path goes from left subtree, root, and right subtree. So the first element in the preorder will always be the root of the tree. In in-order traversal, because the root in the middle, the elements before the root belong to the left subtree, and the elements after the root belong the right subtree. Using the same method, we can also divide the elements in the preorder list to the two branches, and recursively solving the parent nodes and its children nodes in two branches to complete reconstructing the tree. Also, there are exceptions when the subtree we construct has none or only one element (e.g. leaf nodes), and this special case has to be coded under a if/else condition.

    So that's my (partial) solution and explanation of this exercise, if you have any creative / easier way of solving, please comment below and we can discuss and elaborate on it :)

F.Y.I
We can check our grade for test one online if you go to the CSC148 website and click "Grade" on the side bar. I hope this answered your question @Sunny Deng (http://hi-im-sunny.blogspot.ca)