Question 1 of 7: Binary Tree

Question 1: Binary Tree (20 marks: 3 functions)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Approach. The interface exposes no way to reach a node's data except through get_left_child, get_right_child, value, and is_empty; every function below is a pure structural recursion built only from those four (plus delete_node for the deletion). Because delete_node only accepts a leaf, "delete all leaf nodes" can only ever be implemented as one pass that deletes each current leaf — the interface gives no way to delete an internal node, so a second pass (deleting the leaves this pass exposes) is a separate call, not a side effect of this one.

1. compute_sum — sum of all entries

An empty subtree contributes 0; otherwise the total is the node's own value plus the sum of both subtrees.

int compute_sum(BTree tree) {
    if (is_empty(tree) == 0) return 0;             /* empty: no value to add */
    return value(tree)
         + compute_sum(get_left_child(tree))
         + compute_sum(get_right_child(tree));
}

2. delete_leafs — remove every current leaf, one pass

For each child of the current node, check whether that child is itself a leaf (both of its children are absent); if so, delete it directly via delete_node — the only operation the interface permits on a leaf. If the child is not a leaf, recurse into it instead, so the pass still reaches every level of the tree, deleting a leaf wherever one is found this pass. The root is a special case: it has no parent to unlink it from, so if the whole tree is a single node, that node is itself the "leaf" being deleted and the function must return an empty tree.

void delete_leafs_below(BTree tree) {
    if (is_empty(tree) == 0) return;
    BTree l = get_left_child(tree), r = get_right_child(tree);
    if (l != NULL) {
        if (is_empty(get_left_child(l)) == 0 && is_empty(get_right_child(l)) == 0)
            delete_node(l);                        /* l is a leaf: remove it */
        else
            delete_leafs_below(l);                 /* not a leaf yet: recurse deeper */
    }
    if (r != NULL) {
        if (is_empty(get_left_child(r)) == 0 && is_empty(get_right_child(r)) == 0)
            delete_node(r);
        else
            delete_leafs_below(r);
    }
}

BTree delete_leafs(BTree tree) {
    if (is_empty(tree) == 0) return tree;          /* empty tree: nothing to do */
    if (is_empty(get_left_child(tree)) == 0 && is_empty(get_right_child(tree)) == 0) {
        delete_node(tree);                          /* the whole tree is one leaf */
        return NULL;
    }
    delete_leafs_below(tree);
    return tree;                                    /* root survives, its leaves are gone */
}

3. compute_depth — depth of the tree

Depth is measured as the number of edges on the longest root-to-leaf path (an empty tree has depth $-1$ so a single node correctly comes out at depth $0$):

int compute_depth(BTree tree) {
    if (is_empty(tree) == 0) return -1;
    int dl = compute_depth(get_left_child(tree));
    int dr = compute_depth(get_right_child(tree));
    return 1 + (dl > dr ? dl : dr);
}