CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
lightning_missile
lightning_missile

Reputation: 3002

Floor implementation in binary search tree

Consider this statement by Robert Sedgewick in his booksite:

If a given key key is less than the key at the root of a BST, then the floor of key (the largest key in the BST less than or equal to key) must be in the left subtree. If key is greater than the key at the root, then the floor of key could be in the right subtree, but only if there is a key smaller than or equal to key in the right subtree; if not (or if key is equal to the key at the root), then the key at the root is the floor of key.

I'm extremely confused what happens when the key is greater than the root, particularly when he says: "but only if there is a key smaller than or equal to key in the right subtree". I think he means that, if the key is less than the root, the key is certainly in the left subtree. On the other hand if the key is grater, the key "could be" in the right subtree, so it's possible the key will not be found on the right subtree as well. And based on his floor() method:

public Key floor(Key key)
{
   Node x = floor(root, key);
   if (x == null) return null;
   return x.key;
}

private Node floor(Node x, Key key)
{
   if (x == null) return null;
   int cmp = key.compareTo(x.key);
   if (cmp == 0) return x;
   if (cmp < 0)  return floor(x.left, key);
   Node t = floor(x.right, key);
   if (t != null) return t;
   else           return x;
}

He indeed did check the right subtree, but not the left subtree. But I completely can't come up with an example where the key is greater than the root and yet is smaller than the keys in the right subtree. I really think it's impossible. I'm missing something. Can anyone explain what I'm missing?

Upvotes: 0

Views: 3252

Answers (2)

Rupinder Ghotra
Rupinder Ghotra

Reputation: 59

A simple solution:

            int FloorInBST(Node* root,int data)
            {
              if(root == NULL)
              {
                  return -1;//when MinNode of tree is greater than the input value
              }
              if(root->data == data) return data;

              if(root->data > data)
              {
                  return FloorInBST(root->left, data);//MUST be in left subtree 
              }
              else if (root->data < data)
              {
                  //MAY be in right subtree OR root itself
                  int floor = FloorInBST(root->right, data);
                  return (root->data >= floor ? root->data:floor);
              }
            }

Upvotes: 2

500 - Internal Server Error
500 - Internal Server Error

Reputation: 28839

If you have a tree like (excuse my ASCII art skills)

  3
 / \
1   5

And you are looking for floor(4), then

  1. the search key is greater than root
  2. there is no key in the right sub-tree smaller than the search key, so
  3. the result is the root key (3).

Upvotes: 2

Related Questions