Trees and Linked Lists

Trees and Linked Lists are useful for creating intertwined data structures.  Creating a map of connected elements is both efficient and complicated.  It’s efficient in design, but it requires a very firm understanding in both the elementary ideas of the language (and its functions) as well as the end goal you are trying to achieve.

Trees contain varying type instances as “nodes” or “leaves” in the larger system.  Stemming from a root (so far, a specific integer), each node can contain a certain number of other trees, or None types.  The Trees are often represented as a Linked List (where any subservient Tree is a list inside of the dominant list—which can extend infinite times if need be).  This allows the programmer and the user to find specific information via indexing.

Trees (specifically binary trees) can be analyzed by which route the program takes to read the nodes in the tree (traversals): Pre-Order, In-Order, and Post-Order.

The Pre-Order traversal starts at the root, then travels to the left subtree, and works through the various levels from left to right.

As an example:

ROOT

/    \

A            B

/    \        /    \

C       D    E       F

The Pre-Order Traversal will start at the root (ROOT), then move to the first left node (A), then move to the left subtree (C), and since there is another child, continue to that one (D).  At this point, the left subtree is covered, so it will move to the right subtree (B) and follow the same pattern (adding E and then F).  Altogether, this would layout the Pre-Order Traversal as: [ROOT, A, C, D, B, E, F]

Using the same example, the In-Order Traversal will start at the deepest level on the left side (C), move to its parent (A), and since there is another child on that level continue there (D).  since that subtree is done, it will move up again on the left side, which takes it too the root (ROOT).  Now that the left subtree is done, it will continue to the deepest level on the right subtree, but staying on the left side (E), then it will follow the same pattern as the left side (adding B and then F).  Altogether, this would layout the In-Order Traversal as: [C, A, D, ROOT, E, B, F].

Between the two of these traversals, a unique tree can be constructed and visualized (which results in the Post-Order Traversal—which starts at the deepest level and scrolls the tree left to right for each subtree, resulting in [C, D, A, E, F, B, ROOT].