# Properties of Binary Trees

## Prerequisites

### Properties of Binary Trees

#### Introduction

• A binary tree is a type of tree in which each each node has at most two child branches.

#### Notation

• n is the number of nodes.
• nk is the number of nodes with degree k.

#### n = n0 + n1 + n2

• 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 n1 + 2n2

• Each node has k branches extending from it (where k is the degree of the node).
• There will be a total of n1 branches extending from the nodes with degree 1.
• There will be a total of 2n1 branches extending from nodes with degree 2.

#### n0 = n2 + 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 = n0 + n1 + n2`
• Therefore the number of branches is:
`n0 + n1 + n2 - 1`
• We also know that the number of branches is:
`n1 + 2n2`
• Therefore:
`n1 + 2n2 = n0 + n1 + n2 - 1`
• This simplifies to:
`n0 = n2 + 1`
• Implications:
• n0 and n2 are not relative to n1
• You can add and remove nodes with degree 1 without affecting n0 or n2

#### The maximum number of nodes at level i is 2i

• 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 2k+1 - 1

• Prerequisites:
• At each level between 0 and k, the maximum number of nodes is 2k
• Summing these together gives:
`2k+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 log2(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 2h
• These are external nodes
• We also know that there are n + 1 external nodes
• Therefore we can assert: n + 1 ≤ 2h
• If we take the log of both sides then log2(n + 1) ≤ h