up vote 1 down vote favorite

I am confused regarding Binary Search Trees (BST) when an element does not exist in the tree.

For example, to search for element "6", would it take 5 comparisons to search for this element?

My understanding is:

  1. Compare root (Not found - move left)

  2. Compare left node (Not found - move left)

  3. Compare left node (Not found - move right)

  4. Compare right node (Not found, move right)

  5. No right node (6 does not exist)

Is my understanding correct? Would it take 5 comparisons to attempt to search for 6 in this BST?

enter image description here

share|cite|improve this question
New contributor
CrDS is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • Yes, you are correct. – Gokul 15 hours ago
  • The first 4 are real comparisons. Whether and how the last one counts is debatable. – Apass.Jack 14 hours ago
up vote 0 down vote accepted

There are only 4 comparisons: the element 6 is compared to the elements 9,7,4,5.

share|cite|improve this answer

Your Answer

CrDS is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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