Google Interview Question
Software Engineer InternsCountry: United States
It works, but best case would be o(log n). It's arguable whether a node -> node traversal would be better, because the ceil is most likely collocated nearby the original value. Of course the supposes that we already have the node we are looking for, not just its value.
Every time we detect a leaf node, this function will print value of 'findval' twice. Its better once we detect the ceil then just return from the function.
public Node ceil(int i) {
largest = null;
largest = ceilInt(root,i);
return largest;
}
private Node ceilInt(Node n, int x){
if(n == null) return largest;
if(n.value > x){
largest = n;
return ceilInt(n.left,x);
}else{
return ceilInt(n.right,x);
}
}
private Node root = null;
private Node largest = null;
Assuming an existing node class with node.left, node.right, and node.value properties, below is a Python solution:
def ceil_bst(node, key):
if node is None:
return None
elif node.value == key:
return node.value
elif node.value < key:
return ceil_bst(node.right, key)
else:
left_value = ceil_bst(node.left, key)
return left_value if left_value else node.value
Similar to search in BST..just keep a reference variable updating the smallest value greater than given node value
see this--
geeksforgeeks.org/floor-and-ceil-from-a-bst/
// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return -1
int Ceil(node *root, int input)
{
// Base case
if( root == NULL )
return -1;
// We found equal key
if( root->key == input )
return root->key;
// If root's key is smaller, ceil must be in right subtree
if( root->key < input )
return Ceil(root->right, input);
// Else, either left subtree or root has the ceil value
int ceil = Ceil(root->left, input);
return (ceil >= input) ? ceil : root->key;
}
copied from geeksforgeeks, thought will help others..
public static int ceilingValue(BTNode node, int value, int currCeil)
{
if(node == null)
return Integer.MIN_VALUE;
int nextCeil = 0;
if(node.data < currCeil && value < node.data)
currCeil = node.data;
if(value >= node.data)
nextCeil = ceilingValue(node.right, value, currCeil);
else
nextCeil = ceilingValue(node.left, value, currCeil);
if(nextCeil == Integer.MIN_VALUE)
return currCeil;
else
return nextCeil;
}
A simple solution would be to find the successor of the key. Well but the given key may exist or may not exist.
case 1: given key exist in the tree... then its simple to find its successor.
case 2: given key doesn't exist in the tree... In this case, we will first try to find the key in the tree and we will find the successor of the last element before we hit the null.
Time complexity: O(log n)
//just do a inorder traversal and then store collection in an array, and then traverse over it
//O(n) time and O(n) space
vector<int > vec;
int *inorder(node *root)
{
if(root ==NULL) return;
else
{
inorder(root->left);
vec.push_back(root->data);
inorder(root->right);
}
return vec;
}
vector<int>::const_iterator it;
//now traverse the vec
int trave(vector *vec,int key)
{
it=vec.begin();
while(*it <=key)
{
it++;
}
cout<<*it++;
}
If it's a binary search tree, then by "ceil" and the example given, i assume that you are looking for the element which immediately succeeds the given value. i.e.: 13 => 15
You have to handle two cases:
1.) The successor is your right child
2.) The successor is your ancestor
This assumes that we already have a pointer to the target node we are trying to get the ceil of. It's just a way to do an inorder traversal given a start-node, and not a traversal of the entire tree.
int ceil(const node* n){
// Handle our right child
node* curr = n;
if(curr->right){
while(curr->right){
curr = curr->right
}
return curr;
}
// Get our ancestor. We go up until we are no longer a left child
while(curr->parent && curr->parent->left != curr){
curr = curr->parent;
}
return curr; // Would return NULL if it's invalid
}
Here is my non-recursive solution. Note: It assumes that we are asked to return the successor even if the given key is in the tree.
int GetSuccessor (CNode* root, int key)
{
int lastBig = Int32.Max;
CNode* current = root;
while ( current != null )
{
if (key < current->data)
{
lastBig = current->data;
current = current->left;
}
else
{
current = current->right;
}
}
return lastBig;
}
Java solution using static variable and in order traversal
private static boolean done = false;
public void findCeil(Node root, int key){
if(root == null)
return;
findCeil(root.getLeft(), key);
if(!done){
if(root.getData() > key){
System.out.println("The ceiling of " + key + " is: " + root.getData());
done = true;
}
}
findCeil(root.getRight(), key);
}
With python and lazy evaluation
class Node(object):
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right
def ceiling(node, val):
"""Celing value
>>> tree = Node(8,
... Node(3,
... Node(2, None, None),
... Node(6, Node(4, None, None), None)),
... Node(12,
... Node(10, None, None),
... Node(15, None, None)))
>>> ceiling(tree, 13)
15
>>> ceiling(tree, 4)
6
>>> ceiling(tree, 8)
10
"""
def greater(node, val):
if node is None:
return
if node.value > val:
for left in greater(node.left, val):
yield left
yield node
for right in greater(node.right, val):
yield right
try:
return next(greater(node, val)).value
except StopIterator:
return
Call this function Ceil(root,input, -1)
//If input is more than the max key in BST, return -1
int Ceil(node *root, int input, int ans)
{
// Base case
if( root == NULL )
return ans;
// If root's key is equal or smaller, ceil must be in right subtree
// So iterate with previous value - possibly minus one if its going right.
if( root->key <= input )
return Ceil(root->right, input, ans);
// Else, either left subtree or root has the ceil value
// parent must be a possible candidate - iterate further
// to left to find smaller value than parent
return Ceil(root->left, input, root->key);
}
This is can be done in big-oh(log n) complexity.
The question needs to return the strictly next larger but smaller than anything for a given element.
And finding next larger takes big-oh (h).
find_node_closer_to_k(self,k,closer_value):
if self.value == k
self.value = closer_value
next_larger(self)
else:
if self.value > k:
if self.value <= closer_value:
closer_value = self.value
find_node_closer_to_k(self.left,k,closer_value)
else:
outcome = next_larger(self.parent)
else:
if self.value <= closer_value:
closer_value = self.value
find_node_closer_to_k(self.right,k,closer_value)
else:
outcome = next_larger(self.parent)
def next_larger(self):
if self.right is not None:
return self.right.find_min()
current = self
while current.parent is not None and current is current.parent.right:
current = current.parent
return current.parent
find_node_closer_to_k takes big-oh(log n) and next_larger takes(log n)
so overall time complexity is big-oh(log n)
O(NLogN) - Using In-Order Traversal
Given the Key find the Ceiling Value in BST
Step1 : Use In-order Traversal to Traverse the entire Tree into a List - O(NLogN)
Step 2: Use Binary search on the List to find the first Number Greater than the Given Key. - O(N)
The First Number you find in the List will be your Ceiling Value.
Time Complexity = O(NLogN) + O(N) = O(NLogN)
Here's my iterative solution:
public class Main {
static class Node {
int x;
Node left;
Node right;
Node(int x) {
this.x = x;
}
}
public static void main(String[] args) {
Node root = new Node(8);
root.left = new Node(4);
root.right = new Node(12);
root.left.left = new Node(2);
root.left.right = new Node(6);
root.right.left = new Node(10);
root.right.right = new Node(14);
for(int i = 0; i < 16; i++) {
System.out.println(String.format("%d %d", i, ceil(root, i)));
}
}
public static int ceil(Node root, int x) {
Node current = root;
int c = -1;
while (current != null) {
if (current.x == x) {
return current.x;
}
if (current.x < x) {
current = current.right;
} else {
c = current.x;
current = current.left;
}
}
return c;
}
}
There will be three cases
input <--value whose ceil is to be searched
1) either the root.key == input --> in this case return the root.key
2) either the root.right < input --> in this case root will be in the right subtree
3) else the root will be in the left subtree or will be equal to root.key
class node{
int key;
node left;
node right;
public node(int val){
key = val;
left = null;
right = null;
}
}
public class ceil{
public static int Ceil(node root, int input){
if(root == null)
return -1;
if(root.key == input)
return root.key;
if(root.key < input)
return Ceil(root.right, input);
int ceil = Ceil( root.left , input);
return (ceil >= input) ? ceil : root.key;
}
}
this part of code will satisfy all the cases for sure:
int findCeil(node* root, int num, int foundVal=-1)
{
if(root)
{
if(num > root->data)
findCeil(root->right, num, foundVal);
else if(num==root->data)
return root->data;
else
findCeil(root->left, num, root->data);
}
else
return foundVal;
}
Assume all node values are positive. -1 is an unvalid node value.
void findCeiling(node n, int key) {
if (n == NULL) return;
if (key < n.value) {
finalResult = n.value;
findCeiling(n.left, key);
} else {
findCeiling(n.right, key);
}
}
To call this:
int finalResult = -1;
findCeiling(root, key);
std::cout << (finalResult == -1) ? "No ceiling value exists" : finalResult;
just traverse in reverse of inorder starting from right most. Store the immediate greater value known. When the first node you hit less then the input print the immediate greater value.
public class BinarySearchTree {
private class Node {
int value;
Node left;
Node right;
public Node(int val) {
value = val;
left = null;
right = null;
}
}
Node root = null;
private int keyCeiling(int key, Node currNode) {
if(currNode == null) return -1;
int ceiling = -1;
if(key == currNode.value) ceiling = currNode.value;
else if(key < currNode.value) {
ceiling = currNode.value;
int ceil = keyCeiling(key, currNode.left);
ceiling = (ceil == -1) ? ceiling : ceil;
}
else {
int ceil = keyCeiling(key, currNode.right);
ceiling = (ceil == -1) ? ceiling : ceil;
}
return ceiling
}
public void findCeiling(int key) {
if(root == null) {
System.out.println("Empty binary search tree");
return;
}
int ceilValue = keyCeiling(key, root);
if(ceilValue == -1)
System.out.println("Not found ceiling value for " + key);
else
System.out.println("Ceiling value for " + key + " is " + ceilValue);
}
}
Please let me know if I have missed out any corner cases.
to keep stuff simplier, you have to use recursion:
assuming
typedef struct binNode{
struct binNode* left
struct binNode* right
int payload
}* Node;
my solution is
findceil(Node node, searchValue, foundValue){
if(node!=NULL){
if(node.value>=searchValue)findceil(node.right,searchValue,node.payload);
/*watchout: you want keep MAX value*/
else findceil(node.left,searchValue,foundValue);
}else printf("Ceiling value: %d",node.payload);
}
I think it can simply be done using recursion in the following way.It just traverse the bst in a recursive way which will take the same time as that required to traverse a bst. You can test the below code:
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
}
void findCeil(node_t *root,int data)
{
if(root->data==data)
findCeil(root->right,data);
else if(root->data<data)
findCeil(root->right,data);
else if(root->data>data)
{
printf("The value found is %d ",root->data);
return;
}
}
int main()
{
node_t *tree=newNode(3);
tree->left=newNode(2);
tree->left->left=newNode(1);
tree->right=newNode(6);
tree->right->right=newNode(7);
tree->right->left=newNode(5);
findCeil(tree,6);
}
What if you call findCeil(tree, 1)? In this case your code would return 3 when the answer should be 2.
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
return n;
}
bool findCeil(node_t *root,int data)
{
if(root == NULL)
return false;
if(findCeil(root->left, data))
return true;
if(root->data > data) {
cout << "ciel = " << root->data << endl;
return true;
}
if(findCeil(root->right, data))
return true;
return false;
}
int main()
{
node_t *tree=newNode(8);
tree->left=newNode(3);
tree->left->left=newNode(2);
tree->left->right=newNode(6);
tree->right=newNode(12);
tree->right->right=newNode(15);
tree->right->left=newNode(10);
findCeil(tree,4);
}
#include <stdio.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *n=(node_t *)malloc(sizeof(node_t));
n->data=data;
n->left=NULL;
n->right=NULL;
return n;
}
int findCeil(node_t *root,int data,int result)
{
if(root == NULL) return result;
if(root->data > data)
result = findCeil(root->left,data,root->data);
else if(root->data <= data)
result = findCeil(root->right,data,result);
return result;
}
int main()
{
node_t *tree=newNode(3);
//tree->left=newNode(2);
//tree->left->left=newNode(1);
tree->right=newNode(6);
tree->right->right=newNode(7);
tree->right->left=newNode(5);
printf("The value found 1 is %d\n",findCeil(tree,1,-32760));
printf("The value found 2 is %d\n",findCeil(tree,2,-32760));
printf("The value found 3 is %d\n",findCeil(tree,3,-32760));
printf("The value found 4 is %d\n",findCeil(tree,4,-32760));
printf("The value found 5 is %d\n",findCeil(tree,5,-32760));
printf("The value found 6 is %d\n",findCeil(tree,6,-32760));
printf("The value found 7 is %d\n",findCeil(tree,7,-32760));
return 0;
}
Working code is given below... call function using..
findCeil(root, num, num);
- Rahul June 28, 2013