Trees

Tree data structures

A tree is a widely used abstract data type that has a hierarchical structure, with a root value and subtrees of children with a parent node, represented as a set of linked tree nodes. An essential data structure for storing hierarchical data with a directed flow.

Similar to linked lists and graphs, trees are composed of nodes that hold data.

Nodes are store references to zero or more other tree nodes. Data moves down from node to node. Trees are often displayed with a single node at the top and connected nodes branching downwards.

Tree Varietals

The Trees can come in various shapes and sizes depending on the dataset that was modeled. Some Trees can come with parent nodes referencing many child nodes or some can come deep, with many parent-child relationships.

The structure can be both wide and deep, but each node will always only ever have at most one parent; otherwise, it wouldn't be a tree data structure.

Moving from parent to child is moving down a level. This is referred to as depth. Depth is counting levels down from the root node and height is counting levels up from a leaf node.

Binary Search Tree

A binary tree is a type of tree where each parent can have no more than two children, known as the left child and right child.

Constraints are placed on the data or node arrangement of a tree to solve difficult problems like efficient search.

Further constraints make a binary search tree:

• Left child values must be lesser than their parent.
• Right child values must be greater than their parent.

The constraints of a binary search tree allow us to search the tree efficiently. At each node, we can discard half of the remaining possible values!

Cheatsheet

Trees are useful for modeling data that has a hierarchical relationship that moves in the direction from parent to child.

To recap some terms:

• root: A root is a node that has no parent, there is one root per tree.
• parent: A node that references other nodes, as a hierarchical structure.
• child: Nodes referenced by other nodes(parent).
• sibling: Nodes that have the same parent.
• leaf: Nodes that have no children(depth of the tree).
• level: Height or depth of the tree. Root nodes are at level 1, their children are at level 2, those children’s notes are at level 3, and so on.