Trees

Trees are a subset of graphs, a common structure for maintaining relationships between data, especially spacial ones. Below is a basic binary tree along with common terminology. A binary tree is a subset of trees where nodes can only have at most two children.

Tree-Diagram-Labeled.png

Tree structures can get much more complex. Nodes contain whole classes describing a users account or as little as just a single attribute. Edges can be directed, meaning the relationship between nodes only goes in one direction. Edges can also have weights to convey more about the relationship between nodes. Weights can convey distance, current flow, internet throughput, anything you can come up with.

Traversals

Traversals area good way to understand how one would access a trees data with recursion. Each traversal has base cases and recursive calls, and the order of them create the different traversals. Pre-order visites the root first, then it's left child and then its right child. In-order visits the left children then the root and then the right children. Post-order visits all children before the root is finally visited. Select the different tabs to see how the ordering of the recursive calls effects the traversal.

MAzes

The tree traversal concept can be extended to solving mazes. Each node is a place in the maze you can be and each edge is a direction you can walk. In this example, a maze is made of a 2D array of cells. Each cell has a four variables for the four potential walls, top, left, right, bottom. To traverse the maze a root is placed at the top left corner and all directions are tried recursively, like the traversal algorithm above. When a new cell is found it is marked as visited and added to the tree structure. It is guaranteed by the algorithm that all cells will be reached if all cells are reachable from the root cell.

Dijkstra's algorithm For Mazes

This example is a modified Dijkstra’s algorithm for mazes because mazes contain no cycles or loops. If there was a loop then you would need to check if the alternate path to a node was shorter or not. Dijkstra’s algorithm is an important algorithm for finding the shortest path from one node to another in a graph. The rough idea of the algorithm is to keep an updated list of the shortest know distance to all nodes from your root and explore the graph from the shortest distance. Below a priority queue structure is used to keep the order of the node distances. When key’s are updated they are automatically updated. Dijkstra’s algorithm works with all graphs from spanning trees, like with the maze below, to complete graphs. To begin all the nodes should be labelled with a key and a distance of infinity until they have been discovered.

dijkstra’s algorithm for graphs

in progress…