DSABook – Review*

9.15* Review

This final section contains some review questions about the contents of this chapter.

9.15.1 Quiz: Binary trees

Which statement is false?

Every binary tree has at least one node
Every non-empty binary tree has exactly one root node
Every node in a binary tree has exactly two children
Every non-root node in a binary tree has exactly one parent

Look carefully at the definition for a binary tree.
It states that every binary tree is either empty, or it has a root node and two binary trees as children.
So, every binary tree node has two children, but not every binary tree has a node.

What is the minimum number of nodes in a complete binary tree with height 3?

Start filling in the tree level by level.
Stop when you draw the first node at level 3.

Select the one true statement.

None of the alternatives
Every binary tree is either complete or full
Every complete binary tree is also a full binary tree
Every full binary tree is also a complete binary tree
No binary tree is both complete and full

Not every binary tree is either complete or full.
Not every complete binary tree is full.
Not every full binary tree is complete.
Some complete trees are full.

What is the minimum number of nodes in a full binary tree with height 3?

First, draw a vertical chain of 4 nodes. This is a tree with height 3.
Next, add nodes to make the tree be full.

Suppose T is a binary tree with 14 nodes. What is the minimum possible height of T?

Try drawing this as a complete treee.
That is, build a tree of 14 nodes by filling it in level by level.

What is the minimum number of internal nodes in a binary tree with 8 nodes?

Try drawing some trees. Your best bet is to try and make it full.

9.15.2 Quiz: Example binary tree

Here’s an example binary tree:

How many internal nodes does this tree have?

Anything that is not a leaf node is an internal node. Internal nodes might have 1 or 2 children.

What is the height of this tree?

0
1
2
3
4
5
9
Trees have depth – they do not have height
None of the above

Count the number of steps to the deepest node.

How many leaf nodes does this tree have?

Anything that has no children is a leaf node.

How many nodes in the tree have at least one sibling?

Siblings must have the same parent. If a node has two children, then each such child has a sibling.

How many descendents does the root of this tree have?

Every node except the root is a descendent.

What is the depth of this tree?

0
1
2
3
4
5
9
Trees have height – they do not have depth
None of the above

Nodes have depth.

Which statement is correct?

The tree is neither full nor complete
The tree is complete but not full
The tree is full but not complete
The tree is full and complete

Do any internal nodes have only one child? If so, the tree is not full.
A complete tree fills in nodes level by level, with the bottom level filled in from left to right.

9.15.3 Quiz: Binary tree traversals

Visiting each element in a tree is known as:

“Traversing”
“Sorting”
“Merging”
“Inserting”
“Enumerating”

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a postorder traversal and the order of the nodes as visited by an inorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

True
False

Build yourself a small example tree of about 6 or 7 nodes and see what happens.
Consider the example where the root has value A. In the postorder traversal, the left subtree is printed, then the right subtree, then A. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
We can apply this concept recursively to reconstruct the left subtree and the right subtree.

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a preorder traversal and the order of the nodes as visited by an inorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

True
False

Build yourself a small example tree of about 6 or 7 nodes and see what happens.
Consider the example where the root has value A. In the preorder traversal, that A is printed first. In the inorder traversal, the left subtree comes first, then the A, then the right subtree.
From this information, we always know the root, the contents of its left subtree, and the contents of its right subtree.
We can apply this concept recursively to reconstruct the left subtree and the right subtree.

Answer TRUE or FALSE.

If you are given the order of the nodes as visited by a preorder traversal and the order of the nodes as visited by a postorder traversal, do you have enough information to reconstruct the original tree? Assume that the nodes all have unique values.

True
False

Consider this example: The preorder traversal prints ABC, and the postorder traversal prints CBA. Can you determine the original tree from this information?
In general, if a node has only one subtree, then the preorder and postorder traversals do not give you enough information to determine which side the subtree goes on.

Answer TRUE or FALSE.

When you print out the nodes of binary tree, the leaf nodes appear in the same relative order for the preorder, inorder, and postorder traversals.

True
False

Take a small binary tree with three or four leaf nodes and see what happens with the traversals.
Since all 3 traversals print the left subtree before the right subtree, the leaves have to get printed in the same order.

The n nodes in a binary tree can be visited in:

O(n) time
O(1) time
O(\log(n)) time
O(n \log(n)) time
O(n^2) time

This would be done by a traversal. How much work does a traversal do at each node?
Each node is visted once, with constant time spent at each.

Why does function preorder2() presented in the Traversal section make only half as many recursive calls as function preorder()?

Because half of the pointers are null
Because there are half as many nodes
Because there are half as many leaf nodes
Because only internal nodes get called

All nodes will eventually get called
The number of nodes in the tree does not change based on the algorithm used to traverse it.
The Full Binary Tree Theorem tells us that roughly half of all pointers in a binary tree are null. No recursive call is made for these pointers by preorder2.

9.15.4 Quiz: Binary heaps

Which feature of heaps allows them to be efficienty implemented using an array?

Heaps are complete binary trees
Heaps are binary trees
Heaps are binary search trees
Heaps are full binary trees

A heap is not a BST.
In general, just being a binary tree (or even a full binary tree) is not enough to let something be implemented using an array.

In a max-heap containing n elements, what is the position of the element with the greatest value?

0
n-1
n+1
n
2*n+1
2*n+2
Possibly in any leaf node
The leftmost leaf node
The rightmost leaf node

Remember this is a max-heap. So where is the biggest element?
It is at the root. So, what position holds the root?

In a max-heap containing n elements, what is the position of the element with the smallest value?

Possibly in any leaf node
n-1
n+1
n
2*n+1
2*n+2
0
The leftmost leaf node
The rightmost leaf node

Remember this is a max-heap. So where is the smallest element?
It has to be at the bottom.
But, it could be anywhere at the bottom.

Consider a node R of a complete binary tree whose value is stored in position i of an array representation for the tree. If R has a left child, where will the left child’s position be in the array?

2*i+1
i+1
i+2
2*i+2
\lfloor (i-1)/2 \rfloor

If you have a right sibling, it is at i+1.
If you have a left sibling, it is at i-1.
If you have a parent, it is at \lfloor (i-1)/2 \rfloor.
If you have a right child, it is at 2*i+2.
If you have a left child, it is at 2*i+1.

Consider a node R of a complete binary tree whose value is stored in position i of an array representation for the tree. If R has a left sibling, where will the left sibling’s position be in the array?

i-1
i+1
i+2
2*i+2
\lfloor (i-1)/2 \rfloor

If you have a parent, it is at \lfloor (i-1)/2 \rfloor.
If you have a right child, it is at 2*i+2.
If you have a left child, it is at 2*i+1.
If you have a right sibling, it is at i+1.
If you have a left sibling, it is at i-1.

Consider a node R of a complete binary tree whose value is stored in position i of an array representation for the tree. If R has a parent, where will the parent’s position be in the array?

\lfloor (i-1)/2 \rfloor
i+1
i+2
2*i+2
2*i+1

If you have a right sibling, it is at i+1.
If you have a left sibling, it is at i-1.
If you have a right child, it is at 2*i+2.
If you have a left child, it is at 2*i+1.
If you have a parent, it is at \lfloor (i-1)/2 \rfloor.

Consider a node R of a complete binary tree whose value is stored in position i of an array representation for the tree. If R has a right child, where will the right child’s position be in the array?

2*i+2
i+1
i+2
2*i+1
\lfloor (i-1)/2 \rfloor

If you have a right sibling, it is at i+1.
If you have a left sibling, it is at i-1.
If you have a parent, it is at \lfloor (i-1)/2 \rfloor.
If you have a left child, it is at 2*i+1.
If you have a right child, it is at 2*i+2.

Which of these is a true statement about the worst-case time for operations on heaps?

Both insertion and removal are better than linear
Insertion is better than linear, but removal is not
Removal is better than linear, but insertion is not
Neither insertion nor removal are better than linear

Insert works by putting the new element at the end of the array, and moving it up the tree as appropriate.
So its worst-case cost is proportional to the depth of the tree.
Remove works swapping the element to remove with the one at the end of the array. Then move that moved item up or down the tree, as appropriate.
So its worst-case cost is proportional to the depth of the tree.

9.15.5 Quiz: Heapsort

Answer TRUE or FALSE.

Heapsort (as the code is written in this chapter) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

True
False

What happens when two equal values are in separate branches of the tree?
Can the one appearing later in the array move up in the tree?

A disadvantage of Heapsort is:

It is not stable (that is, records with equal keys might not remain in the same order after sorting)
It needs a lot of auxilliary storage
Its average case running time is O(n^2)
None of these answers

Heapsort does not need auxilliary storage.
Heapsort runs in O(n \log(n)) time.
Equal-valued records might be in different sides of the heap, and can get out of relative order.

In which cases are the time complexities the same for Heapsort?

Worst and Average
Worst and Best
Best and Average
Worst, Average and Best

Does Heapsort’s cost vary according to the order of the array input values?
No, it does not matter what order the input values have.
However, the best case occurs when all the values are same.

(Assuming no duplicate key values) The order of the input records has what impact on the number of comparisons required by Heapsort (as presented in this chapter)?

There is a constant factor difference
None
There is a big difference, the asymptotic running time can change

Can Heapsort’s behaviour change depending on outcome of a comparison?
Yes, it changes things a little bit in that it might move things up and down the heap more or less.
But this does not matter, because removing a value from the heap normally costs \log(n).

What is the worst-case time for Heapsort to sort an array of n records that each have unique key values?

O(n \log(n))
O(n)
O(\log(n))
O(n^2)
O(n^n)

Does Heapsort’s number of comparisons depend on the particular order of the input array?
Only a little bit, Heapsort still does basically the same work regardless of input data order.

What is the running time of Heapsort when the input is an array where all key values are equal?

O(n)
O(n^2)
O(\log(n))
O(n ^ n)
O(n \log(n))

Heapsort has the same asymptotic cost in the best, average, and worst cases, but only if the key values are all unique.
If you have a heap with all equal key values, what will the siftdown operation do?
In that case, siftdown will always return immediately, resulting in a constant time operation. Since Heapsort calls siftdown n times, the total cost is O(n).

How much auxilliary space or overhead (beyond the array holding the records) is needed by Heapsort?

O(1)
O(\log(n))
O(n)
O(n^2)

Heapsort does not require any auxilliary arrays.