Trees & BST

Single correct

• A4
• B2
• C10
• D5

T                   S
I:   Inorder        L: left subtree, node, right subtree
II:  Preorder       M: node, left subtree, right subtree
III: Postorder      N: left subtree, right subtree, node

Single correct

• AI – L, II – M, III – N
• BI – M, II – L, III – N
• CI – N, II – M, III – L
• DI – L, II – N, III – M

Single correct

• A$\dfrac{n-2}{2}$
• B$\dfrac{n-1}{2}$
• C$\dfrac{n}{2}$
• D$\dfrac{n+1}{2}$

Single correct

• AInorder traversal of $T$ can be determined from $V$
• BRoot node of $T$ can be determined from $V$
• CPreorder traversal of $T$ can be determined from $V$
• DPostorder traversal of $T$ can be determined from $V$

typedef struct node {
  int val;
  struct node *left, *right;
} node;

int foo(node *p) {
  int retval;
  if (p == NULL)
    return 0;
  else {
    retval = p->val + foo(p->left) + foo(p->right);
    printf("%d ", retval);
    return retval;
  }
}

Single correct

• A3 8 5 13 11 10
• B3 5 8 10 11 13
• C3 8 16 13 24 50
• D3 16 8 50 24 13

Answer key coming soon

Single correct

• A$\Theta(n \log n)$
• B$\Theta(n)$
• C$\Theta(\log n)$
• D$\Theta(1)$

Answer key coming soon

Single correct

• A10, 11, 12, 15, 16, 18, 19, 20
• B11, 12, 10, 16, 19, 18, 20, 15
• C20, 19, 18, 16, 15, 12, 11, 10
• D19, 16, 18, 20, 11, 12, 10, 15

Answer key coming soon

Single correct

• A$\Theta(n^4)$
• B$\Theta(n^2)$
• C$\Theta(n^2 \log n)$
• D$\Theta(n^3)$

Answer key coming soon

Single correct

• A$\Theta(\log n)$
• B$\Theta(\log n + k)$
• C$\Theta(k \log n)$
• D$\Theta(n \log k)$

Answer key coming soon

Single correct

• AI, II and III
• BI, II and IV
• CI, III and IV
• DII, III and IV

Single correct

• A4 and 15 respectively
• B3 and 14 respectively
• C4 and 14 respectively
• D3 and 15 respectively

Answer key coming soon

Single correct

• A2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20
• B2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12
• C7, 2, 6, 8, 9, 10, 20, 17, 19, 15, 16, 12
• D7, 6, 2, 10, 9, 8, 15, 16, 17, 20, 19, 12

Answer key coming soon

Single correct

• A+ - 1 6 7 * 2 ˆ 5 - 3 4 *
• B- + 1 * 6 7 ˆ 2 - 5 * 3 4
• C- + 1 * 7 6 ˆ 2 - 5 * 4 3
• D1 7 6 * + 2 5 4 3 * - ˆ -

Answer key coming soon

Single correct

• A63 and 6, respectively
• B64 and 5, respectively
• C32 and 6, respectively
• D31 and 5, respectively

Single correct

• AI and IV only
• BII and III only
• CII and IV only
• DII only

Single correct

• A$\Theta(\log n)$ for both insertion and deletion
• B$\Theta(n)$ for both insertion and deletion
• C$\Theta(n)$ for insertion and $\Theta(\log n)$ for deletion
• D$\Theta(\log n)$ for insertion and $\Theta(n)$ for deletion

Single correct

• A65
• B67
• C69
• D83

Single correct

• ASQPTRWUV
• BSQPTUWRV
• CSQPTWUVR
• DSQPTRUWV

typedef struct treeNode* treeptr;

struct treeNode
{
    treeptr leftMostChild, rightSibling;
};

int DoSomething (treeptr tree)
{
    int value=0;
    if (tree != NULL) {
        if (tree->leftMostChild == NULL)
            value = 1;
        else
            value = DoSomething(tree->leftMostChild);
        value = value + DoSomething(tree->rightSibling);
    }
    return(value);
}

Single correct

• Anumber of internal nodes in the tree.
• Bheight of the tree.
• Cnumber of nodes without a right sibling in the tree.
• Dnumber of leaf nodes in the tree.

Single correct

• A$O(1)$
• B$O(\log n)$
• C$O(n)$
• D$O(n \log n)$

Answer key coming soon