Ceil value in a Binary Search Tree #2393
Description
Ceil value for any number x in a collection is a number y which is either equal to x or the least greater number than x.
Problem: Given a binary search tree containing positive integer values. Find ceil value for a given key in O(lg(n)) time. In case if it is not present return -1.
Ex.1. [30,20,40,10,25,35,50] represents level order traversal of a binary search tree. Find ceil for 10.
30
/ \
20 40
/ \ / \
10 25 35 50
Answer: 20
Ex.2. [30,20,40,10,25,35,50] represents level order traversal of a binary search tree. Find ceil for 22
30
/ \
20 40
/ \ / \
10 25 35 50
Answer: 25
Ex.2. [30,20,40,10,25,35,50] represents level order traversal of a binary search tree. Find ceil for 52
30
/ \
20 40
/ \ / \
10 25 35 50
Answer: -1