Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

256 BINARY TREES [CHAP. 10

(b) Compare ITEM=33 with the root, 60. Since 33<60, move to the left child, 30. Since 33>30, move to the

right child, 55. Since 33<55, move to the left child, 35. Now 33<35, but 35 has no left child.

Hence add ITEM=33 as a left child of the node 35 to give the tree in Fig. 10-27(a). The shaded edges indicate

the path down through the tree during the insertion.

Fig. 10-27

10.9. Supposendata itemsA 1 ,A 2 ,...,ANare already sorted, i.e.,A 1 <A 2 <···<AN.

(a) If the items are inserted in order into an empty binary treeT, describe the final treeT.

(b) What is the depthdof the final treeT.

(c) Comparedwith the average depthd∗of a binary tree withnnodes for (i)n=50; (ii)n=100;

(iii)n=500.

(a) The treeTwill consist of one branch which extends to the right as pictured in Fig. 10-27(b)

(b) The branch ofThasnnodes; henced=n.

(c) It is known thatd∗=clog 2 n, wherec≈ 1 .4. Hence: (i)d( 50 )= 50 ,d∗( 50 )≈9;

(ii)d( 100 )= 100 ,d∗( 100 )≈10; (iii)d( 500 )= 500 ,d∗( 500 )≈12.

10.10. Suppose the following list of letters is inserted into an empty binary search tree:

J, R, D, G, W, E, M, H, P, A, F, Q

(a) Find the final treeT.(b) Find the inorder traversal ofT.

(a) Insert the nodes one after the other to obtain the treeTin Fig. 10-28(a)

Fig. 10-28