# Binary Trees

## Structure

A Binary Tree is a Tree with the additional constraint that each Node has
**at most 2 children** referred to as "left" and "right" children.

## Sub-types

A Binary Tree is **full** when all Nodes have **exactly either 0 or 2 children**.

A Binary Tree is **complete** when all Nodes on every level, except possibly the last level,
are full and all Nodes are as far left as possible.

A Binary Tree is **balanced** when it's height is `O(log(n))`, where `n`
is the number of Nodes.

The exact definition of "balanced" differs for different types of Trees. But for Binary Trees, in the most
perfect case, where the Binary Tree is complete AND all non-leaf-Nodes have 2 children
and all leaf-Nodes have zero children, the Tree has `(2^h)-1` Nodes, where `h`
is the height of the Tree. Or, to flip it around, deriving the height from the number
of Nodes instead of the other way around, by using
Logarithms, we can derive the **height
of a perfectly balanced Binary Tree** from the number of Nodes to be
`log _{2}(n + 1)`

This example is the "perfect" case though. More generally, a Binary Tree is "balanced" when it's height
is `O(log(n))`.

A **Binary Search Tree** is a Binary Tree with the
**additional constraint** that the value of each Node is **greater than all values in the left
sub-Tree** and **less than all values in the right sub-Tree**.

## Properties

**Nodes** have two properties: **depth** and **height**.
The depth of a Node `n` is the number of edges between `n` and the root Node.
The height of a Node `n` is the number of edges between `n` and the deepest leaf
in it's sub-Tree.

A **Binary Tree** itself only has one variable property: **height**.
The height of a Binary Tree is the **height of it's root Node**.

## Algorithms and Operations

A number of operations are more straightforward on a Binary Search Tree because of the additional ordering constraint.

Please see Binary Search Tree Algorithms for implementations and notes on operations like insert, delete, rotate, max value, min value, traverse and search.