CMS 702 · Everything Left in the Lecture Notes

Answer. An array is the simplest possible hash-style map: the key is the index i, the value is the element stored there, and the "hash function" is the identity function · the key is the slot number, so no transformation and no collision is possible.

The value at A[i] is found by address arithmetic, not by searching:

Because the machine computes that address in a fixed number of steps regardless of how large the array is, the lookup is O(1) · constant time. This is precisely the property hashing tries to buy for arbitrary keys such as strings: the hash function converts a non-numeric key into an index so that it too can be reached in one step.

A  =  Int Array(10)     base address = 1000
      element size = 4 bytes

 key (index):  0    1    2    3    4  …
 value:      [35] [33] [42] [10] [14] …
 address:    1000 1004 1008 1012 1016

A[3]  →  1000 + (3 × 4)  =  1012  →  value 10

Example 1

root = [2, 1, 3],  K = 2

      2
     / \
    1   3

In-order = 1, 2, 3. The node after 2 is 3.

Example 2

root = [3, 2, 1],  K = 3

      3
     /
    2
   /
  1

In-order = 1, 2, 3. Nothing follows 3 · it is the largest value in the tree.

The page-13 assignment

root = [20, 8, 22, 4, 12,
        N, N, N, N, 10, 14]
K = 8

          20
         /  \
        8    22
       / \
      4   12
         /  \
       10    14

In-order = 4, 8, 10, 12, 14, 20, 22.

What the notes recorded

In-order    = B, D, A, G, E, C, H, F, I
Pre-order   = A, B, D, C, E, G, F, H, I
Post-order  = D, B, G, E, H, I, F, C, A

Reconstruction from pre-order + in-order

1. First of the pre-order is the root → A. In the in-order, B D lies to its left and G E C H F I to its right.
2. Left sub-tree: pre B D, in B D → root B; D is after B in the in-order, so D is B's right child.
3. Right sub-tree: pre C E G F H I, in G E C H F I → root C; G E left, H F I right.
4. Under C, left: pre E G, in G E → root E with G as its left child. Right: pre F H I, in H F I → root F with H left and I right.

The tree

              A
            /   \
          B       C
           \     /  \
            D   E     F
               /     / \
              G     H   I

Note that this tree is not a binary search tree · its in-order traversal is not alphabetical. It is an ordinary binary tree, which is why the traversals must be read off the structure rather than guessed from the ordering.

Worked example from the notes

Pre-order  = F, B, A, D, C, E, G, I, H   [Root,L,R]
Post-order = A, C, E, D, B, H, I, G, F   [L,R,Root]

1. Root = first of pre = last of post = F.
2. Second of pre = B → root of the left sub-tree. In the post-order, everything up to and including B is A, C, E, D, B → the left sub-tree; the remainder H, I, G → the right sub-tree.
3. Left: pre B A D C E, post A C E D B → root B; its left child is A (next in pre, and A ends the left block in post), its right child is D, whose children are C and E.
4. Right: pre G I H, post H I G → root G; next in pre is I, whose child is H.

            F
          /   \
         B     G
        / \      \
       A   D      I
          / \    /
         C   E  H

Full binary tree

        1
       / \
      2   3
     / \
    4   5

Every node has 0 or 2 children. Node 3 is a leaf (0 children); nodes 1 and 2 have two each. No node has exactly one child.

Perfect binary tree

        1
       / \
      2   3
     / \ / \
    4  5 6  7

Every internal node has exactly 2 children and all leaves are on the same level. Here h = 2, so leaves l = 2² = 4 and nodes n = 2³ − 1 = 7 ✓

Complete binary tree P.12

        1
       / \
      2   3
     / \  /
    4  5 6

Every level filled except possibly the last, whose leaves lean left · node 3 has a left child but no right sibling for it. This is the exact diagram from the notes.