1. Give pseudocode for an algorithm that accepts a BST node and an integer k and
ID: 3904848 • Letter: 1
Question
1. Give pseudocode for an algorithm that accepts a BST node and an integer k and retuns ethsmaes element in the BST rooted at that node. For example, the tree rooted at node A below contains the values 5, 10, 15, 20, and 25. The 4th smallest element in this tree is 20, so the problem instance with node A and k = 4 should return 20. 20 10 25 15 The behavior of the algorithm is undefined if k is too small or too large; e.g., calling the algorithm with k =-1 can return anything. In adlition to the usual value, left, right, and parent fields, the BST nodes have a count feld that stores the number of nodes in the tree rooted at this node. The count values appear in te diagram as small numbers below each node. Hint: I recommend a recursive algorithmExplanation / Answer
In a BST , for a given node, all the nodes in its left subtree are smaller and all the nodes in the right sub tree are greater than the given node.
Each node in the BST contains the count of the number of nodes in the tree rooted at the given node. Thus for any given node, the value of count for its left child gives the number of nodes in its left subtree and the value of count for the right child stores the number of nodes present in the right subtree. Hence count value of the left child gives number of nodes smaller than the given node.
Assume that the root is having N nodes in its left subtree. If K = N + 1, root is Kth smallest node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)th smallest element. We can note that we require the count of elements in left subtree only.
The pseudo code is as follows:
start:
if k<0 or k>root.count
return -1
goto stop
if K = root.leftChild.count + 1
root node is the K th smallest node.Return root
goto stop
else if K > root.leftChild.count
K = K - (root.leftChild.count + 1)
root = root.rightChild
goto start
else
root = root.leftChild
goto start
stop:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.