Binary search trees (HL)

The binary search tree shown was built by inserting the values 50, 30, 70, 20, 40, 60, 80 and 35 in that order.

(a) Write down the sequence of values produced by an in-order, a pre-order and a post-order traversal. [3]

(b) State the number of nodes examined (including the node holding 35) when searching for the value 35, starting at the root. [1]

(c) State which of the three traversals visits the values in ascending order. [1]

A student claims that the tree shown is a binary search tree (BST) in which, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. The height of a tree is the number of edges on the longest path from the root to a leaf.

(a) State the value held in the root node. [1]

(b) State the number of leaf nodes in the tree. [1]

(c) State the height of the tree. [1]

(d) The tree is not a valid BST. Identify the node that breaks the BST property and explain why. [2]

A greengrocer’s stock system stores product names in a binary search tree, ordered alphabetically. The following names are inserted, in this order, into an empty tree:

kiwi, fig, pear, apple, grape, lime, plum, mango, date

(a) Sketch the binary search tree after all nine names have been inserted. [3]

(b) State the number of nodes that are compared with the search value when searching the tree for cherry, and state the outcome of the search. [1]

The diagram shows a binary search tree of integers.

Two deletions are carried out, in this order:

1. delete(70)
2. delete(35), where a node with two children is replaced by its in-order successor.

(a) Explain how the node holding 70 is deleted. [2]

(b) Describe how the node holding 35 is deleted. [2]

(c) State the pre-order traversal of the tree after both deletions. [2]

The integers 12, 19, 27, 33, 41, 56, 68 are inserted, in this order, into an empty binary search tree.

(a) Describe the shape of the resulting tree. [1]

(b) State the number of nodes visited when searching for 68 in this tree. [1]

(c) Suggest an order of insertion of the same seven values that would produce a tree of the smallest possible height. [1]

(d) Explain how the order in which data is inserted affects the efficiency of searching a binary search tree. [2]

A pre-order traversal of a binary search tree outputs the following values:

40, 25, 10, 32, 28, 36, 60, 52, 75, 68

(a) Sketch the binary search tree. [3]

(b) State the post-order traversal of the tree. [2]

The following Python code is intended to insert a value into a binary search tree. The function returns the root of the (sub)tree after the insertion. It is called as root = insert(root, value).

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(node, key):
    if node is None:
        return ___A___
    if key < node.key:
        node.left = ___B___
    elif key > node.key:
        ___C___
    return node

(a) State the code needed at A, B and C. [3]

(b) The values 7, 3, 9, 3, 1 are inserted, in this order, into an empty tree using the completed function. State the output of an in-order traversal of the tree and explain what happens to the second 3. [2]

(c) State the worst-case time complexity of insert for a tree holding n values. [1]

The diagram shows a binary search tree. Each node has attributes key, left and right. Consider the following recursive Python function.

def mystery(node, lo, hi):
    if node is None:
        return 0
    if node.key < lo:
        return mystery(node.right, lo, hi)
    if node.key > hi:
        return mystery(node.left, lo, hi)
    return 1 + mystery(node.left, lo, hi) + mystery(node.right, lo, hi)

The function is called as mystery(root, 40, 70), where root refers to the node holding 50.

(a) State the value returned. [1]

(b) State the purpose of the function. [1]

(c) State the number of nodes (not None references) that are visited during this call. [1]

(d) Explain why the function does not need to visit the left subtree of a node whose key is less than lo. [2]

A school library system stores about 20 000 book records, each identified by a unique numeric ID. New books are added and old books removed every day, records are frequently looked up by ID, and an end-of-term report lists every book in ID order.

Compare the suitability of a binary search tree, a sorted array and a singly linked list (kept in ID order) for storing these records. [6]

In this question, the height of a binary search tree is the number of edges on the longest path from the root to a leaf. A tree with a single node has height 0.

(a) Show that a binary search tree of height 4 can hold at most 31 values. [2]

(b) Calculate the minimum possible height of a binary search tree that holds 1000 distinct values. [2]

(c) State the maximum number of nodes that must be compared to determine whether a value is in a tree of 1000 values when the tree has:

(i) the minimum possible height; [1]

(ii) the maximum possible height. [1]