Binary Search Trees Questions and Answers

Answer: D

The element that can never be third is 5.

The only complete binary search tree on 1 to 15 has root 8, then 4 and 12, then 2, 6, 10 and 14, and the odd numbers as leaves. In a BST every node must be inserted after all its ancestors, so the first element is 8 and the second is 4 or 12.

The third element can therefore be the other child of the root, or a child of the second element: 4 (order 8, 12, 4), 2 (8, 4, 2) and 10 (8, 12, 10) are all possible.

5 sits on the fourth level, below 8, 4 and 6, so at least three elements must come before it, and it can be inserted fourth at the earliest.

Answer: A

The true statement is Inorder traversal of \(T\) can be determined from \(V\).

An inorder traversal of a binary search tree visits the left subtree, the node, then the right subtree, so it always lists the keys in increasing order, whatever the tree's shape. Sorting V therefore gives the inorder traversal without knowing T.

The root is the first value inserted, and the shape of the tree depends on the whole insertion order, so the root, the preorder and the postorder traversals all change with that order. For example, inserting 1, 2, 3 and 2, 1, 3 gives different roots and different preorders.

Answer: C

In-order traversal of a binary search tree gives the keys in Non-decreasing order.

In a binary search tree, every key in a node's left subtree is less than (or, if duplicates are allowed, not greater than) the node's key, and every key in its right subtree is greater. In-order traversal visits the left subtree, then the node, then the right subtree, so it lists the keys in ascending order.

'Non-decreasing' is the precise term when duplicate keys may occur. The traversal is never unsorted, and decreasing or non-increasing order would come from visiting the right subtree first, a reverse in-order traversal.

Answer: B

The impossible sequence is 3, 240, 398, 256, 399, 258.

In a binary search each node examined narrows the range in which 258 must lie. Following this sequence:

• 3 is less than 258, go right: the range is now above 3.
• 240 is less than 258, go right: above 240.
• 398 is greater than 258, go left: between 240 and 398.
• 256 is less than 258, go right: between 256 and 398.
• 399 lies outside that range, so it cannot be the next node examined.

The other three sequences stay inside their shrinking ranges at every step; for example 453, 200, 448, 210, 363, 258 narrows to (200, 453), (200, 448), (210, 448), (210, 363), all containing 258.

Answer: A

The key classes the binary search tree as an example of the divide and conquer technique.

Searching a binary search tree follows the principle of binary search: at each node one comparison decides which subtree can contain the key, and the other subtree is discarded, so the problem is repeatedly split and only one part pursued.

A greedy algorithm builds a solution by locally best choices, backtracking explores and abandons partial solutions, and dynamic programming stores solutions of overlapping subproblems. None of these describes how a binary search tree divides its search space.

Answer: A

The traversal is inorder.

Inorder traversal visits the left subtree, then the node, then the right subtree. In a binary search tree every key in the left subtree is smaller than the node and every key in the right subtree is larger, so this order lists all keys in ascending order. For a tree with root 50, left child 30 and right child 70, inorder gives 30, 50, 70.

Preorder visits the node first (50, 30, 70) and is used to copy a tree. Postorder visits it last (30, 70, 50) and is used to delete one. Level order goes level by level from the root, which is not sorted order in general.

Answer: B

Searching a balanced BST takes O(log n) time.

Each comparison moves the search one level down the tree, so the cost is the height of the tree. A balanced tree (AVL, red-black and so on) keeps its height proportional to log n, so a search makes at most about log n comparisons.

O(n) is the worst case of an unbalanced BST that has degenerated into a chain. O(n log n) is the cost of building or sorting, not of one search. O(1) is the average for hashing, not for a search tree.

Answer: C

The traversal is inorder.

In a BST every key in the left subtree is smaller than the node and every key in the right subtree is larger. Inorder traversal visits left subtree, node, right subtree, so it lists the keys in ascending order.

Preorder visits the node before its subtrees and postorder after them, so neither gives sorted output. Level order lists the tree level by level from the root, which is not sorted either.

Answer: A

The inorder successor is always either a leaf node or a node with empty left child.

When the node to be deleted has a right child, its inorder successor is the smallest node in its right subtree, found by going to the right child and then as far left as possible. That node has no left child (otherwise we could go further left), though it may still have a right child.

So it need not be a leaf, it cannot be an ancestor (that happens only when there is no right subtree), and it may have a right child, which rules out 'empty right child'.

Answer: C

The inorder sequence is 4, 5, 6, 9, 10, 11, 12, 13.

Inorder traversal of any binary search tree visits the keys in ascending order, so it is just the given keys sorted. The postorder sequence only fixes the tree's shape: its last element, 6, is the root, with 4 and 5 in the left subtree and 9 to 13 in the right.

Option B is the keys in descending order, which would be a reverse inorder traversal. Options A and D are not sorted, so they cannot be the inorder sequence of a BST.