Solutions to the Practice Questions#

What is a Tree?#

  1. a. Yes, this is a tree. Root: A. Leaf: D. Binary tree
    b. Not a tree, B and C have two parents
    c. Yes, this is a tree. Root: X. Leaves: A, W, and Q. Binary tree
    d. Not a tree. No links
    e. Not a tree. H has two parents
    f. Yes, this is a tree. Root: U. Leaves: M, W, C, B, V, R, and X. Not a binary tree, as E has three children
    g. Yes, this is a tree. Root: G. Leaf: G. Binary tree.

  2. a. Ancestors: grapefruit and lemon. Proper Ancestor: lemon
    b. Descendants: all nodes. Proper Descendants: all nodes but lemon
    c. None
    d. banana
    e. Only banana
    f. banana and kiwi
    g. apple, canteloupe, kiwi, orange, and watermelon
    h. lemon to grapefruit to banana to canteloupe
    i. Does not exist
    j. Does not exist
    k. 3
    l. 2

Back to Questions

Traversals#

  1. a. M, A, H, D, W, C, Q, B, E, V, P, K, G, R, X, T, F, J, S, U
    b. U, E, A, M, Q, W, D, H, C, B, S, V, T, R, G, P, K, X, F, J
    c. Does not exist. This is not a binary tree
    d. U, E, A, M, A, E, Q, W, D, H, D, W, Q, C, Q, E, B, E, U, S, V, S, T, R, G, P, G, K, G, R, T, X, T, S, F, S, J, S, U
    e. U, E, S, A, Q, B, V, T, F, J, M, W, C, R, X, D, G, H, P, K
    f. F, J, M, W, C

  2. ..

    Tree

  3. ..

    Tree

  4. At the start, at the end, and if the tree ends with a rightmost linear section

  5. a. \(44 = 6 \times (8-3) + 2 \times 7\)
    b. \(6~~8~~3 - \times 2~~7 \times +\)
    c. \(+ \times 6 - 8~~3 \times 2~~7\)

Back to Questions

Binary Search Tree#

Back to Questions