1.1  8, 4, 5, 12, 15

1.2

1.3 a, c, d
    e

1.4  T(1) = 1
     T(N) = T(N-1) + O(1)
     O(N)

1.5
    if(cur == null)
        return 0;
    if(cur.myLeft == null && cur.myRight == null)
        return 1;
    int leftLeaves = countLeaves(cur.myLeft);
    int rightLeaves = countLeaves(cur.myRight);
    return leftLeaves + rightLeaves;

1.6 d

1.7 e

2.1
     3
  7     4
9  8  6  12

2.2

       3
    5     4
  7  8  6  12
9

2.3  k/2

2.4
add - O(logN), add node at first open spot. then heapify at most height on leap, which is logN
remove - O(logN), swap root with last node. Remove last node. Then heapify starting at the root, for at most height of heap swaps.

2.5 To remove the smallest value from a balanced BST will be O(logN) because the smallest value is the left-most leaf. To remove the smallest value from a min-heap, is worst-case logN but bast case O(1).


3.
if(isClear(maze, curX, curY)){
    maze[curX][curY] = 'X';

    int[] travelX = {-1, 0, 0, 1};
    int[] travelY = {0, -1, 1, 0};

    for(int i = 0; i < 4; i++){
        if(getPath(maze, curX+travelX[i], curY+travelY[i], endX, endY))
            return true;

    maze[curX][curY] = '.';
}

isClear

if(y < 0 || y > maze[0].length-1)
    return false;
if(maze[x][y] != '.')
    return false;

4.1
O(NlogN), split array in half until size == 1, (logN), merge back together, N.

O(N) Outer for-loop runs n times. Never enter inner for-loop.

O(NlogN) remove from a heap (O(logN) N times.

4.2
O(NlogN) same as above

O(N^2) Outer-loop n times, inner-loop up to n times. 

O(NlogN) same as above.