Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This belongs more to StackOverFlow –  Emmad Kareem Dec 19 '11 at 10:46
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.