Google Interview Question
Site Reliability EngineersTeam: Google Engineering
Country: United States
Interview Type: Phone Interview
@Anonymous: No, the worst case is still Omega(n).
What if we had to print all of them? (or even n/2 of them?).
// Follow the normal pre-order and decide which branch to take
void print_in_range_bst(struct TNode* node, int min, int max, int& sum=0)
{
if(root) {
if(root->data >= min && root->data<=max) {
cout<<root->data<<endl;
sum += root->data;
print_in_range_bst(root->left, min, max, sum);
print_in_range_bst(root->right, min, max, sum);
} else {
// Go right if root's data is smaller than min since all nodes in the left will be smaller than min too.
if(root->data < min) {
print_in_range_bst(root->right, min, max, sum);
}
// Go left if root's data is greater than max since all nodes in the right will be greater than max too.
if(root->data > max) {
print_in_range_bst(root->left, min, max, sum);
}
}
}
}
complexity depends on the range and given nodes in the BST.
But on average would save a lot of unnecessary work since we are preventing those branches.
public int sumRange(Node root, int min, int max) {
if (root == null) return 0;
a = root.value;
if (min <= a && a <= max) {
return a + sumRange(root.left, min, max) + sumRange(root.right, min, max);
else if (a < min)
return sumRange(root.right, min, max);
else if (a > max)
return sumRange(root.left, min, max);
}
}
int rangesum(tree *root, int max, int min)
{
if(!root)
return 0;
if (max < min)
return 0;
if(min == root->data && max == root->data)
return root->data;
if(min<=root->data && root->data <=max)
return (root->data + rangesum(root->left) + rangesum(root->right));
if(min < root->data && max < root->data)
return (rangesum(root->left));
if(min>root->data && max>root->data)
return (rangesum(root->right));
return 0;
}
/* Assuming that the range is inclusive*/
long sumRange(Tree *root, int min, int max)
{
int sum = 0;
/*Error checking*/
if (min > max) {
return 0;
}
/* Base case */
if (root == NULL) {
return 0;
}
if (root->data >=min && root->data <= max) {
sum += root->data;
return (sum + sumRange(root->left, min, max) + sumRange(root->right, min, max));
}
if (root->data > max) {
return sumRange(root->left, min, max);
}
/* Don't really need this if check below - as this is the only condition applicable.
* Left here for clarity.
*/
if (root->data < min) {
return sumRange(root->right, min, max);
}
/* Should not reach here */
return -1;
}
}
Do inorder traversal ...find the least key......than start adding the values untill the max term of the given range arrive....
#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
int a;
struct tree* left;
struct tree* right;
}TREE;
TREE* addNode(TREE* node, int val)
{
if(node==NULL)
{
node=(TREE*)malloc(sizeof(TREE));
node->a=val;
node->left=NULL;
node->right=NULL;
}
else if(val<=node->a)
node->left=addNode(node->left,val);
else if(val>node->a)
node->right=addNode(node->right,val);
return node;
}
void printInorder(TREE* head)
{
if(head==NULL)
return;
printInorder(head->left);
printf(" %d ",head->a);
printInorder(head->right);
}
int sum;
void printSum(TREE* head,int min,int max)
{
if(head==NULL)
return;
printSum(head->left,min,max);
if(head->a>min&&head->a<max)
sum+=head->a;
printSum(head->right,min,max);
}
int main()
{
int arr[]={2,5,9,7,6,-1,0,10,23,12,15,18,14,3,1};
int i;
TREE* head=NULL;
for(i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
head=addNode(head,arr[i]);
printInorder(head);
printf("\n");
int min=5,max=11;
printSum(head,min,max);
printf("%d\n",sum);
return 0;
}
inorder traversal will find the sum but here we are not pruning unnecessary paths and not using the BST property.
So for this questions using full inorder traversal is an overkill but ofcourse an approach to tell your interviewer.
package One;
public class SumTree{
public static void main(String[] args) {
Tre t=new Tre(5);
t.left=new Tre(3); t.right=new Tre(7);
t.left.left=new Tre(2); t.left.right=new Tre(4); t.right.left=new Tre(6); t.right.right=new Tre(8);
int sum=t.getSumBetween(-1, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(sum);
}
}
class Tre{
int value;
Tre left;
Tre right;
public Tre(int v)
{
value=v;
}
public int getSumBetween(int givenMin,int givenMax,int Min,int Max)
{
System.out.println(this.value);
int s=0;
int sleft=0;
int sright=0;
if(givenMin>Max || givenMax<Min || this==null)
{
return 0;
}
if(this.value >=givenMin && this.value<=givenMax)
{
s=this.value;
if(this.left!=null)
{
sleft=this.left.getSumBetween(givenMin,givenMax,Min,this.value);
}
if(this.right!=null)
{
sright=this.right.getSumBetween(givenMin, givenMax, this.value, Max);
}
s=s+sleft+sright;
}
return s;
}
}
int findRange(TreeNode *root, int max, int min)
{
if(root==NULL) return 0;
if(root->value>=min && root->value<=max)
return a+findRange(root->left,max,min)+findRange(root->right,max,min);
if(root->value<min)
return findRange(root->right,max,min);
if(root->value>max)
return findRange(root->left,max,min);
}
Similar to OP's but with an optimization.
- Loler September 25, 2012