Self-test 8:
Binary Tree

True or False

The height of any binary search tree with n nodes is O(log(n)).

Solution

False. In the best case, the height of a BST is O(log n) if it is balanced. In the worst case, however, it can be θ(n).
True or false.

Inserting into an AVL tree with n nodes requires θ(log n) rotations.

Solution

False. There are two explanations.
1. There are cases where inserting into an AVL tree requires no rotations. θ(log n) rotations implies Ω(log n) rotations. Since we have insertions that require no rotations, this means inserting into an AVL tree does not require Ω(log n) rotations and thus it does not require θ(log n) rotations.
2. Inserting into an AVL tree may require looking at O(log n) nodes, but it only needs to perform at most 2 rotations to fix the imbalance. Thus inserting into an AVL tree requires O(1) rotations, which is not θ(log n).
Common mistakes include thinking that rotations are needed for each node in the inserted node's ancestry line and thinking that we were asking for the runtime of insertion and not the number of rotations required.
The level of a node is defined as the depth of it + 1. For example, the level of the root is 1 and that of its direct children is 2. The maximum number of nodes on level i of a binary tree is:
1. 2^(i-1)
2. 2^i
3. 2^(i+1)
4. 2^[(i+1)/2]
(The operator '^' indicates power for this question.)
Solution

A is correct. Proof: by Induction, Introduction base: i=1 (root). The number of nodes is: 2^(i-1) = 2^0 = 1.
Induction hypothesis: Assume that for i ≥ 1, the maximum number of nodes on level i-1 is 2^(i-2).
Induction step: Since each node in a binary tree has a maximum degree of 2. Therefore, the maximum number of nodes on level i is 2*2^(i-2) which is 2^(i-1).

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Solution

B is correct. The following are all possible unlabeled binary trees.

Note that nodes are unlabeled. If the nodes are labeled, we get more number of trees.

Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29. Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?
1. 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
2. 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
3. 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
4. 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Solution

A is correct. Inorder traversal of a BST always list elements in an increasing order. Among all four options, a) is the only increasing order sequence.
Consider a node X in a binary tree. Given that X has two children, and that Y is the inorder successor of X. Which of the following is true about Y?
1. Y has no right child.
2. Y has no left child.
3. Y has both children.
4. None of the above.
Solution

B is correct. Since X has both children, Y must be the leftmost node in the right sub-tree of X, so it won't have a left child.
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
1. 2
2. 3
3. 4
4. 6
Solution
B is correct. The constructed binary search tree will be:
```
                    10
                  /     \
                 1       15
                 \      /  \
                  3    12   16
                    \
                     5
```
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
1. 10, 20, 15, 23, 25, 35, 42, 39, 30
2. 15, 10, 25, 23, 20, 42, 35, 39, 30
3. 15, 20, 10, 23, 25, 42, 35, 39, 30
4. 15, 10, 23, 25, 20, 35, 42, 39, 30
Solution
D is correct. The following is the constructed tree.
```
            30
         /      \
        20       39
       /  \     /  \
     10    25  35  42
      \   /
      15 23
```
Which of the following traversals is sufficient to construct the original BST from given traversals 1) Inorder 2) Preorder 3) Postorder
1. Any one of the given three traversals is sufficient
2. Either 2 or 3 is sufficient
3. 2 and 3
4. 1 and 3
Solution

B is correct. When we know either preorder or postorder traversal, we can construct the BST. Note that we can always just sort any given traversal and get the inorder traversal, as an inorder traversal of BST is always sorted.
Consider the following code. What does the function print() do in general? The function print() receives the root of a BST and a positive integer k as arguments.
```
  // A BST node
struct node {
    int data;
    struct node *left, *right;
};

int count = 0;

void print(struct node *root, int k)
{
    if (root != NULL && count <= k)
    {
        print(root->right, k);
        count++;
        if (count == k)
          printf("%d ", root->data);
       print(root->left, k);
    }
}
```
1. Prints the k-th smallest element in BST.
2. Prints the k-th largest element in BST.
3. Prints the leftmost node at level k from root.
4. Prints the rightmost node at level k from root.
Solution

B is correct. The function basically does a reverse inorder traversal of the given BST. The reverse inorder traversal visits the nodes in a reverse sorted order. Whenever a node is visited, count is incremented by 1 and the data of the node is printed only when count becomes k. Therefore, the k-th largest element would be printed.
After inserting the elements 71, 65, 84, 69, 67, 83 to an empty binary search tree in the given order, the element at the maximum depth is
1. 65
2. 67
3. 69
4. 83
Solution
B is correct. The constructed tree is:
```
       71
     /    \
    65     84
     \     /
     69   83
     /
    67 
```

Self-test 8: Binary Tree

Self-test 8:
Binary Tree