Binary Search Tree

  • Differentiate binary trees from binary search trees based on the complete ordering property.

The tree illustrated below is a special binary tree called binary search tree

In a binary search tree, for a value stored at a node,

  1. All the values in its left subtree are smaller than it.
  2. All the values in its right subtree are greater than it.

The property described above is often referred to as the complete ordering property of BSTs.

Exercise Which of the following trees are Binary Search Tree?

Solution

(B) is the correct answer!

Resources