#### Introduction

- A binary tree is a type of tree in which each each node has at most two child branches.
- This article lists its various properties.

#### Notation

`n`is the number of nodes.`n`is the number of nodes with degree k._{k}

#### n = n_{0} + n_{1} + n_{2}

- Any node in a binary tree will have a degree of 0, 1, or 2.
- The total number of nodes is equal to the number of nodes with degrees 0, 1, and 2.

#### The number of branches is n - 1

- Each node in the tree (except the root) will will have a branch leading to it.

#### The number of branches is equal to n_{1} + 2n_{2}

- Each node has k branches extending from it (where k is the degree of the node).
- There will be a total of n
_{1}branches extending from the nodes with degree 1. - There will be a total of 2n
_{1}branches extending from nodes with degree 2.

#### n_{0} = n_{2} + 1

- The number of vertices of degree 2 is always 1 more than the number of vertices of degree 0.
- Proof:
- We know that the number of branches is n - 1 and that:
n = n

_{0}+ n_{1}+ n_{2} - Therefore the number of branches is:
n

_{0}+ n_{1}+ n_{2}- 1 - We also know that the number of branches is:
n

_{1}+ 2n_{2} - Therefore:
n

_{1}+ 2n_{2}= n_{0}+ n_{1}+ n_{2}- 1 - This simplifies to:
n

_{0}= n_{2}+ 1

- We know that the number of branches is n - 1 and that:
- Implications:
- n
_{0}and n_{2}are not relative to n_{1} - You can add and remove nodes with degree 1 without affecting n
_{0}or n_{2}

- n

#### The maximum number of nodes at level i is 2^{i}

- The number of nodes at any level is at most twice as many as at the previous level.

#### The maximum number of nodes in a tree with height `k` is 2^{k+1} - 1

- Prerequisites:
- At each level between 0 and k, the maximum number of nodes is 2
^{k} - Summing these together gives:
2

^{k+1}- 1

#### The maximum height of a tree with `n` nodes is `n - 1`

- In the worst case scenario a skewed tree would have one node at each level
- There would be
`n`levels - The distance between the bottom level and the root would be
`n - 1`

#### The minimum height of a tree with `n` internal nodes is `log`_{2}(n + 1)

_{2}(n + 1)

- In the best case scenario, the nodes will be arranged as a full tree.
- We know that the maximum number of nodes at the bottom level is
`2`^{h}- These are external nodes

- We also know that there are
`n + 1`external nodes - Therefore we can assert:
`n + 1`≤ 2^{h} - If we take the
`log`of both sides then`log`≤ h_{2}(n + 1)