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

  • $\begingroup$ Yes, you are correct. $\endgroup$
    – Gokul
    Nov 15, 2018 at 18:29
  • $\begingroup$ The first 4 are real comparisons. Whether and how the last one counts is debatable. $\endgroup$
    – John L.
    Nov 15, 2018 at 18:58

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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