Searching a binary search tree for a specific value

Question

suppose numbers from 1 to 1000 are saved in a binary search tree and we want to find 363. Which of the following sequences cannot be the order of elements while reaching the searched value?

• 925, 202, 911, 240, 912, 245, 363
• 924, 220, 911, 244, 898, 258, 362, 363
• 2, 252, 401, 398, 330, 344, 397, 363
• 2, 399, 387, 219, 266, 382, 381, 278, 363

I converted them to rooted binary search trees but I couldn't figure out what should be wrong with them. More precisely, I don't know how to check BST properties in such sequences.

Answer 1

You need to check the following conditions:

(i) The left subtree of a node contains only nodes with keys less than the node's key.

(ii) The right subtree of a node contains only nodes with keys greater than the node's key.

So let's do this for case one by looking at the values for the nodes we traverse until we either find 363 or until one of the conditions is violated:

     925
    /   \
   202
  /   \
       911 
      /   \
     240
    /   \
        912

Woops! We see that $912 > 911$ even though it is in the left subtree of $911$ hence condition (i) is violated.

Let me know if you can do the other cases or if you need more help. Hope this helps.

Answer 2

For each list, split it in two lists: one with numbers smaller than 363 and one with bigger. The first list should be sorted ascending, the other descending.

That is because when you search in a BST you compare the node value to your query and get rid of the branch witch doesn't include your value.

• 925 911 912 -> bad
• 924 911 898; 220 244 258 362 -> good
• 2 252 330 344; 401 398 397-> good
• 2 219 266 278; 399 387 382 381 -> good