December 31st 2018

A data structure can be defined as a specialized format for accessing, organizing, and modifying data. There are lots of different data structures but the ones most commonly encountered in programming can be broken down into two camps.

- Array
- Stacks
- Queues
- Linked Lists
- Hash Tables

- Trees
- Graphs

*(This is of the Linux File System Structure)*

We can use trees for:

- Manipulating hierarchical data
- Manipulating sorted lists
- Making information easier to search for (tree transversal)
- Routing algorithms
- And so much more!

**Root**is the first node of a tree**Edge**is the link between two nodes**Parent**is a node that has an edge to a child**Child**is a node which has a parent**Leaf**is a node which does not have a child**Height**is the length of the longest path to a leaf**Depth**is the length of the path to its root**Subtree**are descendants of a node**Transversing**is passing through nodes in a specific order**Levels**are generations of a node**Keys**are the value of a node based on a search operation

- A tree is set up hierarchically with data being arranged from more general to specific.
- Trees are made up of nodes which contain data or value and are connected by edges.
- Nodes can have child nodes but if they do not have any children they are called a leaf.
- Each leaf node will be unique.
- Children nodes are independent of one another.
- The first node of the tree is the root.
- If the root is connected to another node then the root is also called a parent node and the connection is a child node.
- There can be multiple parent nodes on a tree but only one root. If a tree has n-nodes then it will always have (n-1) edges.

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Binary trees can be very useful for searching when they are balanced. Any node in the data structure can be reached by starting at the root node and repeatedly following references to either the left or right child. In a binary tree, a degree of every node is at most two.
Depending on how nodes are arranged in a binary tree, it can be **full**, **complete** and **perfect**:

**Full binary tree**: each node has exactly 0 or 2 children (but never 1)and all leaf nodes are on the same level.**Complete binary tree**: when all levels except the last one are full with nodes.**Perfect binary tree**: when all the levels (including the last one) are full of nodes.

Binary Search Trees or BST for short are a particular application of binary trees. BST has at most two nodes (like all binary trees). However, the values are in such a way that the left children value must be less than the parent and the right children is must be higher.

Traversal describes the process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. There are different ways of traversing a Binary Tree depending on the order that the nodes are visited: in-order, pre-order and post-order.

**In-Order Traversal**: visit nodes on this order: left, parent, right.**Post-Order Traversal**: visit nodes on this order: left, right, parent.**Pre-Order Traversal and DFS (Depth First Search)**: visit nodes on this order: parent, left, right

There are lots of different basic data structures that can be used in programming. Some data structures are linear and are useful for accessing data in a sequential manner. Linear structures have the drawback of taking a lot of time to search through for a data set. A tree is a data structure where a node has zero or more children. Trees with 2 children or less are called binary trees. If a binary tree is sorted where the left value is less than the parent and the right child is higher then it is considered a binary search tree. There is also a variety of ways to transverse a binary tree depending on the order in which nodes are visited.