2

I was just coming up with an example for an algorithm I'm working on and realised I don't understand whether the following binary tree is a binary search tree:

        3
      /   \
     2     4
   /   \
  1     3

The reason I'm unsure is because:

  • there are duplicates in the tree (3)

Is the rule with binary search trees that all values in the left subtree are smaller than the root?

2 Answers 2

2

This is binary search tree..

1) If you traverse it in IN-ORDER you will get the sorted list
2) Every element on the left node is less than root node (in value)
3) As far as the duplication is concerned, it is okay, since the in-order traversal will return 1,2,3,3,4 
0

Yes, the left subtree's nodes' key value is less then the node's key value; and the right subtree's nodes' key value is greater then the node's key value; [here is the binary_serch_tree wiki]: http://en.wikipedia.org/wiki/Binary_search_tree

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.