Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 252

3. do exercise 2 assuming the tree is stored in an array.

4. Write a function that, given the root of a binary search tree, deletes the smallest node and

returns a pointer to the root of the reconstructed tree.

5. Write a function that, given the root of a binary search tree, deletes the largest node and

returns a pointer to the root of the reconstructed tree.

6. Write a function that, given the root of a binary search tree, deletes the root and returns a

pointer to the root of the reconstructed tree. Write the function replacing the root by (i) its
in-order successor and (ii) its in-order predecessor.

7. draw a nondegenerate binary tree of five nodes such that the pre-order and level-order

traversals produce identical results.

8. Write a function that, given the root of binary tree, returns the width of the tree, that is, the

maximum number of nodes at any level.

9. a binary search tree contains integers. For each of the following sequences, state whether it

could be the sequence of values examined in searching for the number 36 . If it cannot, state why.

7 25 42 40 33 34 39 36
92 22 91 24 89 20 35 36
95 20 90 24 92 27 30 36
7 46 41 21 26 39 37 24 36

10. draw the binary search tree (Bst) obtained for the following keys assuming they are inserted

in the following order: 56 30 61 39 47 35 75 13 21 64 26 73 18 .

there is one almost complete Bst for the previous keys. draw it.

List the keys in an order that will produce the almost complete Bst.

assuming that the almost complete tree is stored in a one-dimensional array num[1..13] ,
write a recursive function for printing the integers in post-order.

11. an imaginary “external” node is attached to each null pointer of a binary tree of n nodes. how

many external nodes are there?

If I is the sum of the levels of the original tree nodes and E is the sum of the levels of the
external nodes, prove that E - I = 2 n . ( I is called the internal path length .)

Write a recursive function that, given the root of a binary tree, returns I .

Write a nonrecursive function that, given the root of a binary tree, returns I .

12. draw the binary tree whose in-order and post-order traversals of the nodes are as follows:

In-order: G D P K E N F A T L

post-order: G P D K F N T A L E

13. draw the binary tree whose pre-order and in-order traversals of the nodes are as follows:

pre-order: N D G K P E T F A L

In-order: G D P K E N F A T L