Midterm Review

Front

Insert the following numbers into a binary search tree in order: 9, 20, 7, 8, 10, 22, 21. Where will the number 10 be located?

Back

As the right child of 8.

Front

Insert the numbers 15, 10, 20, 5, 12, 17, 25 into a BST. What is the in-order traversal of the tree?

Back

5, 10, 12, 15, 17, 20, 25

Front

What is the time complexity of merge sort?

Back

O(nlogn)

Front

Which of the following correctly describes a stack and a queue?
Stack: Last In, First Out (LIFO);
Queue: First In, First Out (FIFO).

Back

Stack: Last In, First Out (LIFO);
Queue: First In, First Out (FIFO).

Front

Write a recursive method to count the total number of leaf nodes in a binary tree. What is the base case for this recursive function?

Back

When the node has no children.

Front

What is the height of the following binary tree?
10
/ \
5 15
/ \
3 7

Back

3

Front

Which of the following is true for a binary search tree (BST)?
Options:
All left children are greater than the parent node.
All right children are smaller than the parent node.
All left children are smaller and all right children are greater than the parent node.
It is not necessary for a BST to have ordered nodes.

Back

All left children are smaller and all right children are greater than the parent node.

Front

Which sorting algorithm has the worst-case time complexity of O(n^2)? Options: Merge Sort, Quick Sort, Bubble Sort

Back

Bubble Sort

Front

What is the result of a pre-order traversal of this binary tree?
8
/ \
3 10
/ \
1 6

Back

8, 3, 1, 6, 10

Front

What is the average-case time complexity for searching in a balanced binary search tree (BST)?

Back

O(logn)