Readme.md

Floor Value in Binary Seacrh Tree(BST)

---

What is Floor Value in BST ?

Let suppose we are given a key , and we have to find floor value with respect of the key value , present int our BST.

The greatest value present in BST which is just smaller than the key given is called Floor value

---

EXAMPLE =>

For the given BST , as shown above , if

1. key= 7 >> Floor value=6
2. key= 12 >> Floor value=10
1. key= 3 >> Floor value=2

**By default if floor value not present in BST for the given Key, then Code will return -1 and if the node's value and key value is same then return node's value as Floor value .

---

Approach to find Floor Value in BST:

A easy approach is to traverse the BST using any traversale method(Inorder or Preorder or Postorder) and keep updating the closest smaller or same element.

 1. Start from root
 2. if root->data ==key return node's data as floor value
 3. else if root->data>key then floor value must be at left subtree, Go to root->left
 4. Else floor value must be at root's right subtree , Go to root->right
 5. If after traversal floor value is not found then return -1. 

---

Time & Space Complexity :

Time Complexity : O(h) for the traversal , [h is height of BST]
Space Complexity : No extra/auxillary space required.