Trees

A tree is a linked list of nodes with a single, root parent. Trees data structures are everywhere in software. The operating systems use them for files. Browsers use them for the HTML Dom.

              root
                |
         -------------
         |           |
       child       child
         |
    -----------
    |    |    |
 child child child

There's a common terminology around trees to help defined the different parts:

Root

The most parent node.

Height

The longest path from the root to the most child node.

Binary tree

A tree in which has at most 2 children, at least 0 children.

General tree

A tree with 0 or more children.

Binary search tree

A tree in which has a specific ordering to the nodes and at most 2 children.

Leaves

A node without children.

Balanced

A tree is perfectly balanced when any node's left and right children have the same height.

Branching factor

The amount of children a tree has.