Binary Search Tree; Write an Algorithm You are given binary search tree (BST) T
ID: 3675813 • Letter: B
Question
Binary Search Tree; Write an Algorithm
You are given binary search tree (BST) T with n nodes with depth d 21og_2(n). For each node x, its key is denoted x. key. Write an algorithm given a BST T and a node x, to counts how many nodes have keys strictly less than that of node x. key. Assume all nodes in the tree have unique keys. Example: For the tree below, consider the node with key 17. There are 7 keys that arc less than 17. The tree T is now augmented by adding for each node x a field x. s that denotes the number of nodes in the subtree below it. The value of x. s for each node s is shown alongside the node in the picture below. Provide an algorithm for solving the problem in (A) assuming that the tree is augmented. Your algorithm should now run in time proportional to the depth of the node x.Explanation / Answer
a.
// to calculate substree count under given root
int GET_SUBTREE_COUNT(ROOT):
if ROOT == NULL:
return 0
else
return GET_SUBTREE_COUNT(ROOT.LEFT) + GET_SUBTREE_COUNT(ROOT.RIGHT)
int COUNT_STRICTLY_LESS_THAN(ROOT, X):
ANS = 0
CURRENT_NODE = ROOT
WHILE (CURRENT_NODE != NULL && CURRENT_NODE.KEY < X.KEY):
ANS = ANS + 1 + (GET_SUBTREE_COUNT(CURRENT_NODE.LEFT) + 1)
CURRENT_NODE = CURRENT_NODE.RIGHT
if (CURRENT_NODE != NULL && CURRENT_NODE.KEY == X.KEY)
ANS = ANS + (GET_SUBTREE_COUNT(CURRENT_NODE.LEFT) + 1)
return ANS
b.
int COUNT_STRICTLY_LESS_THAN(ROOT, X):
ANS = 0
CURRENT_NODE = ROOT
WHILE (CURRENT_NODE != NULL && CURRENT_NODE.KEY < X.KEY):
// all on left side are less than CURRENT_NODE key
if (CURRENT_NODE.LEFT != NULL)
ANS = ANS + CURRENT_NODE.LEFT.S + 1
// add count for current node
ANS = ANS + 1
// move to right
CURRENT_NODE = CURRENT_NODE.RIGHT
if (CURRENT_NODE != NULL && CURRENT_NODE.KEY == X.KEY && CURRENT_NODE.LEFT != NULL)
ANS = ANS + CURRENT_NODE.LEFT.S
return ANS
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.