0.9 Exercises  (Page 2/5)

Chapter 5. binary search trees

Exercises 5.1

For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of height 2, 3, 4, 5, and 6.

Exercises 5.2

What is the difference between the binary-search-tree property and the min-heap property? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or why not.

Exercises 5.3

Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: There is an easy

solution that uses a stack as an auxiliary data structure and a more complicated but elegant solution that uses no stack but assumes that two pointers can be tested for equality.)

Exercises 5.4

Give recursive algorithms that perform preorder and postorder tree walks in Θ(n) time on a tree of n nodes.

Exercises 5.5

Argue that since sorting n elements takes Ω(n lg n) time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of n elements takes Ω(n lg n) time in the worst case.

Exercises 5.6

Suppose that we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequences could not be the sequence of nodes examined?

a. 2, 252, 401, 398, 330, 344, 397, 363.

b. 924, 220, 911, 244, 898, 258, 362, 363.

c. 925, 202, 911, 240, 912, 245, 363.

d. 2, 399, 387, 219, 266, 382, 381, 278, 363.

e. 935, 278, 347, 621, 299, 392, 358, 363.

Exercises 5.7

Write recursive versions of the TREE-MINIMUM and TREE-MAXIMUM procedures.

Exercises 5.8

Write the TREE-PREDECESSOR procedure.

Exercises 5.9

Professor Bunyan thinks he has discovered a remarkable property of binary search trees.

Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a  A, b  B, and c  C must satisfy a ≤ b ≤ c. Give a smallest possible counterexample to the professor's claim.

Exercises 5.10

Show that if a node in a binary search tree has two children, then its successor has no left

child and its predecessor has no right child.

Exercises 5.11

Consider a binary search tree T whose keys are distinct. Show that if the right subtree of a

node x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. (Recall that every node is its own ancestor.)

Exercises 5.12

An inorder tree walk of an n-node binary search tree can be implemented by finding the

minimum element in the tree with TREE-MINIMUM and then making n-1 calls to TREESUCCESSOR. Prove that this algorithm runs in Θ(n) time.

Exercises 5.13

Prove that no matter what node we start at in a height-h binary search tree, k successive calls to TREE-SUCCESSOR take O(k + h) time.

Exercises 5.14

Let T be a binary search tree whose keys are distinct, let x be a leaf node, and let y be its

parent. Show that key[y] is either the smallest key in T larger than key[x]or the largest key in T smaller than key[x].