## Binary Trees / Binary Search Trees

### More Terms

 binary tree A binary tree is a tree in which each node has two children, possibly absent, named the left child and the right child. complete binary tree A complete binary tree is is a binary tree of depth n where all nodes in levels 0 through n - 1 levels inclusive have degree 2 and nodes at level n occupy the leftmost positions in the tree. full binary tree A full binary tree is a binary tree in which all leaves have the same depth and all internal nodes have degree 2. balanced binary tree A balanced binary tree is binary tree where the depth of all leaves is the same or 1 plus the least. degenerate binary tree A degenerate binary tree is a binary tree in which each node has 1 child.   ### Density

At each level d there may be from 1 to 2d nodes.

 level 0: 1 to 20 = 1 node level 1: 1 to 21 = 2 nodes level 2: 1 to 22 = 4 nodes level 3: 1 to 23 = 8 nodes etc.

In a full binary tree of height d there will be 2(d + 1) - 1 nodes.

Consider a tree of height 3.

```1 + 2 + 4 + 8 = 15 = 24 - 1
```

We can recall binary to decimal conversion as a memory aid. Example, convert `1001` to base 10:

```    8  4  2  1
1  0  0  1two  = 8 + 0 + 0 + 1 = 9
or
23 22 21 20
1  0  0  1two  = 23 + 0 + 0 + 20 = 9
```

Consider, convert `1111` to base 10:

```    8  4  2  1
1  1  1  1two  = 8 + 4 + 2 + 1 = 15
or
23 22 21 20
1  1  1  1two  = 23 + 22 + 21 + 20 = 15
```

Note:

``` 24 23 22 21 20
1  1  1  1two
+            1two
-----------
1  0  0  0  0two =  24 = 16

10000two = 1111two + 1two

10000two - 1two = 1111two
```

So,

``` 24  - 1 =  23 + 22 + 21 + 20
```

And, in general,

``` 2(d + 1) - 1 =  2d + 2d - 1 + ... + 21 + 20
```

In a complete binary tree of height d there will be at least 2d nodes. Levels through d - 1 form a full tree and there is at least 1 node in the next level (at the left).

Using the above formula, in the complete part of the tree there are:
`2[(d - 1) + 1] - 1` = `2d - 1`
nodes. Adding one more we get:
`2d - 1 + 1` = `2d`

Thus in a complete binary tree the number of nodes, n is:

```2d <= n <= 2(d + 1) - 1 < 2(d + 1)
or
2d <= n < 2(d + 1)
```

Given the number of nodes, what is the depth of a complete binary tree?

```    log2(2d) <= log2(number of nodes) < log2(2(d + 1))
d <= log2(n) < d + 1
```

Since the depth must be a whole number we get the following, where `n` is the number of nodes and `int()` means discard the fractional part.

Depth of a complete binary tree:

```    d = int(log2(n))
```

Consider a complete binary tree that has 15 nodes. (Draw it and compute `d = int(log2(n))`).

For a full binary tree, with n nodes and height h,

• there are 2d nodes at each level, depth d
• there are a total of 2d + 1 - 1 total nodes
• the worst case depth for any leaf is O(log2 n)   