Challenge: Find Ancestors of a Given Node in a BST

Problem Statement #

In this problem, you have to implement the findAncestors() function to find the ancestor of the node with the value “k”. An illustration is also provided for your understanding.

Function Prototype: #

String findAncestors(Node root, int k);

Here, root is the root node of the Binary Search Tree, and k is an integer value of the node whose ancestors we need to find.

Output: #

It returns all the ancestors of k in the Binary Search Tree in a string format.

Sample Input #

bst = {
		6 -> 4,9
    4 -> 2,5
    9 -> 8,12
    12 -> 10,14
}
where parent -> leftChild,rightChild

k = 10

Sample Output #

6,9,12,

Explanation #

6->9->12->10 is the path from the root to the given node, so 12,9, and 6 are the ancestors of 10. Here’s an illustration of the given challenge: