Question

Let T be a binary search tree. Show how to implement the following operation on T:

countAlllnRange(Key lower, Key upper): Compute and return the number of items in T with key k such that “lower ≤ k ≤ upper”.

Assumption: The ADT Node offers a method “key” which returns the key value of the respective node.

Give the running time of the operation in Big-O notation.

Answer 1

we can do this efficiently using binary tree traversal:

we use inorder traversal as the tree is binary search tree, ans inorder in a binary search tree is sorted :

Algorithm:
initialize tree
Inorder(tree)
Traverse the left subtree, i.e., call Inorder(left-subtree)
Visit the key
Traverse the right subtree, i.e., call Inorder(right-subtree)

thus given algorithm can be designed as:

initialize a variable count=0
countAlllnRange(key current_node=tree starting node,Key lower, Key upper,flag=0):
countAlllnRange(current node.left,lower,upper,flag)
if(flag==0)
if(key is greater than lower && current_node.key() is less than upper):
count++
flag=1
else if(flag==1 && current_node.key() is less than upper)
count++
else if(flag==1)
flag=2
return
else if(flag==2)
return
countAlllnRange(current node.right,lower,upper,flag)

here we take advantage of binary search tree and thus start counting when current key is greater than lower and less than upper
and end when we reach a node where key is greater than upper and return

note the value of variable flag:

when flag=0 means all keys till now are less than lower
when flag=1 means we have begin the count and if current key is less than upper keep counting
when flag=2 means return unconditionally because we have reached a key which is greater than upper

running time of this algorithm is O(n)
as in worst case all keys are within the range(lower,upper)

COMMENT DOWN FOR ANY QUERIES AND,

LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.