educative.io

Recursive Solution

Courses
,
#1

A reader asked us the following question:

I understand that the recursive solution prints the ancestors, but the Q asks to return it as a comma separated string. So, does the solution qualify?

#2

Hi,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your query, the challenge only asks for a comma-separated list so that it can be evaluated later. The main purpose of the challenge is to program a correct algorithm to find the ancestors, not the format in which the output is presented. The recursive and iterative functions both can be used to pass the test case with some modifications. For the recursive solution, we can use a static string in the class scope which will be used to store the resultant string. I have programmed such a solution for you below:

class CheckAncestors {
  public static String result;
  public static String findAncestors(Node root, int k) {
    result = "";
    recursiveFindAncestors(root, k);
    return result;
  }

  // Find the ancestors if target is present in the tree, then return true, else returns false. 
  static boolean recursiveFindAncestors(Node node, int target) 
  { 
    if (node == null)   // base cases 
      return false; 

    if (node.getData() == target) 
      return true; 

    // Add this node if target is present in either left or right subtree of this node
    if (recursiveFindAncestors(node.getLeftChild(), target) || recursiveFindAncestors(node.getRightChild(), target)) 
    { 
      result = node.getData() + "," + result; 
      return true; 
    } 
    return false;   // else return false 
  } 

}

Note that this might not be the most optimized approach in terms of memory usage. However, I just wanted to demonstrate to you that this solution is as valid as the iterative one. I hope this explanation helps.

Thank you for your valuable feedback! If you have any further queries or concerns, please feel free to get in touch again.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative