TREE TRAVERSALS

Given the following tree structure: What is the pre-order traversal of the tree?

1 2 4 5 3 6 8 9 5 7

1 2 3 4 6 7 5 8 9 5

1 2 3 4 5 5 6 7 8 9

5 4 2 1 3 6 7 8 9 5

1 2 4 5 3 6 8 9 5 7

Explanation:

When a preorder traversal is done, you go through the following:

1. ROOT

2. LEFT CHILD

3. RIGHT CHILD

Therefore, starting at the root (1), we go to the LEFT node (2). That node however, is the root/parent of other nodes, so we go left again (4). That node is a parent/root, so we go left (5). Now it's time to go to the right; however, only node 1 has a right child, so going to the right of one we land at (3). That node is the parent/root of more children so we go left (6). Node 6 doesn't have any left children, but it does have a right so we go right (8). Node 8 has a left child to traverse (9) and then a right (5). And we finish the traversal by going to the right of three (7). This is a rather complicated example; however, make sure you can traverse the tree properly. In the above image, you can see the approach of the pre-order traversal. First you go through the roots, then the left trees, then the right trees. Make sure that if you're guiding yourself by the image above, that you don't repeat the nodes that you already traversed. Understanding the algorithm is key.

Example Question #6 : Operations On Data Structures

Traverse and print out this list

List<Integer> integers = new ArrayList<Integer>();

System.out.println(integers.get(0));

System.out.println(integers.get(1));

System.out.println(integers.get(2));

for (int i = 0; i < integers.size()-1; i++) {

System.out.println(integers.get(i));

}

for (int i = 0; i < integers.length-1; i++) {

System.out.println(integers.get(i));

}

for (int i = 0; i < integers.size()-1; i++) {

System.out.println(integers[i]);

}

for (int i = 0; i < integers.size()-1; i++) {

System.out.println(integers.get(i));

}

Explanation:

Use a for loop to traverse the list. The .size() method is used for Lists as opposed to the .length method for arrays. The .get() method is used for Lists as opposed to accessing the index for arrays.

Example Question #1 : Traversals

What's the best way to traverse this list in Swift (iOS)?

var list: [Int] = [0, 1, 2, 3, 4, 5]

var i = 0

for (i; i < list.count; i++) {

println(i)

}

for (var i = 0; i < list.count; i++) {

println(i)

}

for i in list {

println(i)

}

for i in range(list.count) {

println(i)

}

for i in list {

println(i)

}

Explanation:

The correct answer is the best way because it uses Swift's built in "in" operator. In this case, "in" will convert the thing that comes after "in" (so in this case, list) into a range operator. Essentially it will say "i in range(list.count)." This is why the other answer choice that uses "in" is incorrect in terms of the "best" way to traverse a list of integers in Swift.

Example Question #1 : Traversals

Suppose you are given an array of integers:

int array[] = {1,2,3,4,5};

and the following method:

public static void printArray(int[] arr)

{

for (int a = 0; r < arr.length-1; a++)

{

if (a%2==0)

{

System.out.println(arr[a]);

}

}

}

After the method cacll printArray(array) is called, the output would be:

2

4

1

3

1

2

3

4

5

2 4 6

1

3

5

1

3

Explanation:

1

3

The important line here is the if statement, which only executes if (a%2==0) is true, or if the loop counter divided by 2 is 0. A possible error is to divide each element of the array by 2 instead of the loop counter. So the println statement will only execute if the loop counter is even, which happens on the 1st itteration (a=0) and the 3rd itteration (a=2). The for loop ends at arr.length-1, which means that a takes on a maximum value of 3, and not 4 (choosing the option 1 3 5 would mean you did not notice the bounds on the for loop). Finally, println prints a new line every time, so, it is not possible for all the integers to be on one line, as println is executed twice.

Example Question #11 : Standard Operations & Algorithms

public static int[] doWork(int[] arr, int val,int index) {

int[] ret = new int[arr.length + 1];

for(int i = 0; i < index; i++) {

ret[i] = arr[i];

}

ret[index] = val;

for(int i = index + 1; i < ret.length; i++) {

ret[i] = arr[i - 1];

}

return ret;

}

What does the code above perform?

It deletes a value from the array, so long as it is at a given index

It inserts a new value in to an array, adding that value to the existing array

It inserts a new value into an array by overwriting the value that was there before

It searches for a value in the array, storing a new value at the index at which that value was found

It inserts a new value in to an array, adding that value to the existing array

Explanation:

A quesiton like this is most easily understood by doing a careful reading of the code in question. Let's consider each major section of code:

int[] ret = new int[arr.length + 1];

This line of code creates a new array, one that is 1 longer than the array arr.

for(int i = 0; i < index; i++) . . .

This loop copies into ret the values of arr up to index - 1.

(This is because of the i < index condition)

Then, the code stores the value val in ret[index]

for(int i = index + 1; i < ret.length; i++) . . .

It then finishes copying the values into ret.

Thus, what this does is insert a value into the original array arr, returning the new array that is one size larger. (This is necessary because of the static sizing of arrays in Java.)

Example Question #12 : Standard Operations & Algorithms

public static int[] doWork(int[] arr, int val,int index) {

int[] ret = new int[arr.length + 1];

for(int i = 0; i < index; i++) {

ret[i] = arr[i];

}

ret[index] = val;

for(int i = index + 1; i < ret.length; i++) {

ret[i] = arr[i - 1];

}

return ret;

}

Which of the following is a possible error in the first loop in code above?

I. The array arr might be indexed out of bounds.

II. The array ret might be indexed out of bounds.

III. A null pointer exception might occur.

Only I

Both I and III

I , II, and III

Both II and III

Only III

Both I and III

Explanation:

The most obvious possible error is that the array arr might be a null value. You need to check for these kinds of values before using the variables. (If you do arr on a null value, an exception will be thrown.) In addition, it is possible that a value for index might be given that is too large. Consider if index = 100 but arr is only 4 elements long. Then, you will have ret be a 5 value array. When the first loop starts to run, you will go all the way to 99 (or at least attempt to do so) for the index value i; however, once you get to ret = arr, there will be an out of bounds error on arr, which only has indices 0, 1, 2, and 3. Of course, there could be other problems later on with ret, but the question only asks about this first loop.

Example Question #21 : Computer Science

int[] arr = {0,0,0,0,0,0,0,0,0,0};

int arrFill = 0;

int val;

// In here, n items are added.  ArrFill is n.  Presume that n <= 9

// The variable val now contains a new value to be added

Which of the following blocks of code push a new value into arr as though it were a stack?

None of the others

arr[arrFill + 1] = val;

arrFill++;

arr = val;

arrFill++;

arr[arrFill - 1] = val;

arrFill++;

arr[arrFill] = val;

arrFill++;

arr[arrFill] = val;

arrFill++;

Explanation:

Let us presume that the array arr looks like the following list of integers:

{4,51,41,0,0,0,0,0,0,0}

Presume that our new value is 77.

A stack could either push on to the beginning and move everything back one, giving you something like:

{77,4,51,41,0,0,0,0,0,0}

However, none of the options do this.  (No, not even the one that uses the index 0.  This one does not add on to the array so much as replace the first element of it.)

So, the other option is to put it on the "end" of the list.  The variable arrFill is being used for this purpose.  If it is 3, this means that it is the value of the fourth element.  Thus, you can set arr = 77 (where 4 really is arrFill).

This will give you:

{4,51,41,77,0,0,0,0,0,0}

You also need to add one to the value of arrFill.

The other options do not correctly address the array.  They either are too large or too small by one.

Example Question #22 : Computer Science

True or False.

The worst case for insertion into an ArrayList is O(N).

False

True

True

Explanation:

Insertion into an ArrayList is typically O(1). However, since an ArrayList uses an array as its underlying data structure, there can be a need to resize the underlying array. Resizing an array requires creating a new array and copying all the data from the old array to the new array which takes O(N) time.

Example Question #11 : Standard Operations & Algorithms

public static int[] doWork(int[] arr, int val,int index) {

int[] ret = new int[arr.length + 1];

for(int i = 0; i < index; i++) {

ret[i] = arr[i];

}

ret[index] = val;

for(int i = index + 1; i < ret.length; i++) {

ret[i] = arr[i - 1];

}

return ret;

}

What does the code above perform?

It deletes a value from the array, so long as it is at a given index

It inserts a new value in to an array, adding that value to the existing array

It inserts a new value into an array by overwriting the value that was there before

It searches for a value in the array, storing a new value at the index at which that value was found

It inserts a new value in to an array, adding that value to the existing array

Explanation:

A quesiton like this is most easily understood by doing a careful reading of the code in question. Let's consider each major section of code:

int[] ret = new int[arr.length + 1];

This line of code creates a new array, one that is 1 longer than the array arr.

for(int i = 0; i < index; i++) . . .

This loop copies into ret the values of arr up to index - 1.

(This is because of the i < index condition)

Then, the code stores the value val in ret[index]

for(int i = index + 1; i < ret.length; i++) . . .

It then finishes copying the values into ret.

Thus, what this does is insert a value into the original array arr, returning the new array that is one size larger. (This is necessary because of the static sizing of arrays in Java.)

Example Question #12 : Standard Operations & Algorithms

public static int[] doWork(int[] arr, int val,int index) {

int[] ret = new int[arr.length + 1];

for(int i = 0; i < index; i++) {

ret[i] = arr[i];

}

ret[index] = val;

for(int i = index + 1; i < ret.length; i++) {

ret[i] = arr[i - 1];

}

return ret;

}

Which of the following is a possible error in the first loop in code above?

I. The array arr might be indexed out of bounds.

II. The array ret might be indexed out of bounds.

III. A null pointer exception might occur.

Only I

Both I and III

I , II, and III

Both II and III

Only III 