Linked Lists

Linked lists are similar to arrays, thhey both store data, but linked lists consist of nodes that contain a reference to the next node in the list. Basically, a linked list is an ordered list of data. Although the traversal is sequential and so the worst case is that it takes O(n) times to find an element,  these is a major advantage of this to an array.  The size of the list is not need to be known in advance. This means you may add up to infinite elements to the list, while once arrays are full, nothing can be added.

Binary Trees

 Binary Trees and recursion are a important concept taught in this course. A binary tree is made of nodes, where each node consists of  "left" children and  "right" children.  When an item is insterd,  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. Hence binary trees can be 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.

    In pre-order Binary trees,  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.