Binary Trees - Data Structures and Algorithm Analysis - page 190

5.12 Write a recursive function that traverses a binary tree, and prints the value of
every node which has at least four great-grandchildren.
5.13 Compute the overhead fraction for each of the following full binary tree im-
plementations.
(a) All nodes store data, two child pointers, and a parent pointer. The data
field requires four bytes and each pointer requires four bytes.
(b) All nodes store data and two child pointers. The data field requires
sixteen bytes and each pointer requires four bytes.
(c) All nodes store data and a parent pointer, and internal nodes store two
child pointers. The data field requires eight bytes and each pointer re-
quires four bytes.
(d) Only leaf nodes store data; internal nodes store two child pointers. The
data field requires eight bytes and each pointer requires four bytes.
5.14 Why is the BST Property defined so that nodes with values equal to the value
of the root appear only in the right subtree, rather than allow equal-valued
nodes to appear in either subtree?
5.15 (a) Show the BST that results from inserting the values 15, 20, 25, 18, 16,
5, and 7 (in that order).
(b) Show the enumerations for the tree of (a) that result from doing a pre-
order traversal, an inorder traversal, and a postorder traversal.
5.16 Draw the BST that results from adding the value 5 to the BST shown in
Figure 5.13(a).
5.17 Draw the BST that results from deleting the value 7 from the BST of Fig-
ure 5.13(b).
5.18 Write a function that prints out the node values for a BST in sorted order
from highest to lowest.
5.19 Write a recursive function named smallcount that, given the pointer to
the root of a BST and a key K, returns the number of nodes having key
values less than or equal to K. Function smallcount should visit as few
nodes in the BST as possible.
5.20 Write a recursive function named printRange that, given the pointer to
the root of a BST, a low key value, and a high key value, prints in sorted
order all records whose key values fall between the two given keys. Function
printRange should visit as few nodes in the BST as possible.
5.21 Write a recursive function named checkBST that, given the pointer to the
root of a binary tree, will return true if the tree is a BST, and false if it is
not.
5.22 Describe a simple modification to the BST that will allow it to easily support
finding the Kth smallest value in (log n) average case time. Then write
a pseudo-code function for finding the Kth smallest value in your modified
BST.