Saved Bookmarks
| 1. |
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? Explain your answer. (i) 2, 252, 401, 398, 330, 344, 397, 363 (ii) 924, 220, 911, 244, 898, 258, 362, 363 (iii) 925, 202, 911, 240, 912, 245, 363 (iv) 2, 399, 387, 219, 266, 382, 381, 278, 363 (v) 935, 278, 347, 621, 299, 392, 358, 363 |
|
Answer» (i) This is a valid representation of sequence. (ii) This is also a valid representation of sequence. (iii)This could not be the sequence since 240 is encountered after 911 so it must be its left child, and any other node henceforth must be less than 911(parent). But the node 912 breaks this sequence, which is greater than 911 and lies on the left subtree of 911, which violates the basic rule of a Binary Search Tree. (iv)This is also a valid representation of sequence. (v)This could not be a valid sequence since 621 is encountered after 347 so 621 must be its right child, and any other node henceforth must be greater than 347(parent). But this sequence is broken by the node 299 < 347 and lies on the right subtree of 347 which violates the basic rule of a Binary Search Tree. |
|