Consider the following specification for a node object in a binary search tree w
ID: 3915865 • Letter: C
Question
Consider the following specification for a node object in a binary search tree whose keys are integer values. Property N.left N.right N.key N.tree.size The number of nodes in the subtree rooted at node N (including N itself) Description Pointer to left child of N (or null) if no left child exists Pointer to right child of N (or null) if no right child exists An integer containing the element for node N Now, consider the COUNTBETWEEN problem below Input:The root node R of a binary search tree (using the node type defined above), as well as two integers a and b, where aExplanation / Answer
Psedocode is a follows:
CountBetween(root, a, b) :
Declare count = 0
// if root is Null the count will be 0
if root == Null :
return count
if root.key >= a and root.key <= b:
// call recursively the function for left child and right chilf
count = 1 + CountBetween(root.left, a, b) + CountBetween(root.right, a, b)
else
count = CountBetween(root.left, a, b) + CountBetween(root.right, a, b)
Return count
return count
The complexity of this code is O(h) as we are traversing down the tree along the height of the tree.We traversed it first the left child and then the right child.