Week 8 : Impressions of Week 7

               In week 7 we learnt about the data structure called Trees, and more specifically binary trees. Trees are a way to store data, we also learnt that different position in a tree have different names. In the image to the right you will see a binary tree, each circled value in the tree is called a node and the top node, 8 in the tree to the right, is called the root. Trees in computer science are upside down to trees you would find in nature, so the nodes at the bottom with no children (children are nodes extending from other nodes), are called leafs. Trees can have as many children as given to them but the special type of tree called a binary tree can only have two children.

                Since nodes in binary trees can only have two children they have special names, right and left. There is also a special type of binary tree called a binary search tree, the tree mentioned earlier is actually a binary search tree. In binary search trees data in the left subtree of a node is less than the data in the node and data in the right subtree is greater than the data in the node. While learning about binary trees we also learnt about binary tree traversals.

                There are three ways we learnt to travers a binary tree, inorder, preorder and postorder. When traversing inorder you visit the left most unvisited tree, then the node itself then the right tree, always repeating this algorithm recursively, I remembered this by remembering the order of three letters, L, N, and R (LNR) L for left, N for node and R for right. One thing that I noticed when traversing a binary search tree inorder is that you visit the data in the tree in sorted order from least to greatest. When traversing the tree in preorder you first visit the node then the left node then the right node repeating this recursively with each node visited (NLR). With post order you first visit the leftmost node then the right node then the node itself, always repeating this algorithm with each node visited (LRN). The way I remember the algorithms is with the letter orders I have been putting in parentheses. The algorithm for inorder is LNR (left node, the parent node, right node) and I remember this because each combination has L before R and with inorder the ‘N’ is in-between ‘L’ and ‘R’. I remember preorder as the ‘N’ is before (pre) the L and R so NLR. I remember postorder as the ‘N’ is after (post) the L and R so LRN.