Question

DEPTH counting starts at 1 at the root.

Q1 [20 pts.]: Given the following key sequence (6,22,9,14,13,1,8) build the dynamic binary search tree WITHOUT BALANCING IT. How many probes (i.e., comparisons) does it take to determine that key 100 is not in the tree? (In this study case, the root is 6; the next element 22 > 6, so it goes to the right, etc).

Answer 1

Solution: Dynamic Binary Search Tree without balance it is as follows

key sequence (6,22,9,14,13,1,8)

Step 1: Insertion of the 1^st element, i.e., 6 in our case.

Step 2: Insertion of 2^nd element, i.e., 22; Here 22 > 6; therefore, 22 is the right child of 6.

Step 3: Insertion of 3^rd element, i.e., 9; Here 9 > 6, therefore, it's the right children of 6, but 6 already have right children 22; and 9 < 22; therefore 9 is left children of 22.

Step 4: Insertion of 4^th element, i.e., 14; Here 14 > 6 ; 14 < 22 ; 14 > 9. Therefore 14 is right children of 9.

Step 5: Insertion of 5^th element, i.e., 13; Here 13 > 6 ; 13 < 22 ; 13 > 9 ; 13 < 14. Therefore 13 is left children of 14.

.

Step 6: Insertion of 6^th element, i.e., 1; Here 1 < 6; Therefore, 1 is left children of 6.

Step 7: Insertion of 7^th element, i.e., 8; Here 8 > 6 ; 8 < 22 ; 8 < 9. Therefore 9 is left children of 9.

Comparisons to determine key 100 is not in the tree: 2 comparisons will be needed to add 100 to this tree.

Comparison 1: 100 > 6, i.e., 100 is greater than 6, but the right children are already present, so traverse in the Right direction

Comparison 2: 100 > 22, i.e., 100 is greater than 22, and the right children of 22 is not present, so 100 is the right children of 22.

The graph after adding key 100 will be as shown below:

----------------------------------------------------------------------------------------------------------------------------------------------------------

Feel free to ask your queries in the comments, and please upvote if you got a satisfactory answer.