A tree structure is similar to a tree branch. Each branch can contain its own branches. A tree data structure can be used to store a hierarchy in memory. A tree is stored internally in Nodes. Each node of a tree contains the data contained within that node as well as references to each child node. Each child node then contains the references to each of it’s own children. Each child node can only have one parent node. A tree typically has one root node. A tree should also not contain a cycle.

Here’s an image depicting what a tree looks like conceptually:

Advantages/Disadvantages of Trees:

Advantages:

quintessential data structure for storing a hierarchy

necessary for implementing other data structures like Binary Trees, Binary Search Trees (including balanced Binary Search Trees), Tries, Heaps (sometimes implemented in a Tree).

Disadvantages:

slow search

uses more memory then an array

being able to go from child -> parent requires using more memory (to store the reference to the parent in the node).

hard to write algorithms for if you don’t understand recursion well

Special types of trees:

Binary Tree: each node can contain only 0, 1, or 2 children (each node can have a left and right child node)

Binary Search Tree: Binary Tree in which each left child is less than its parent and each right child is greater than its parent. This allows for quick searching.

Trie: a special type of tree which can be used to store Strings/their prefixes and even replace a hash map.