Question

[c++]Please help complete the function of binary tree(contains string data) in a recursive way

std::string findPath (const std::string &s) const; // EFFECTS: Returns the path from the root node to the node with the string s. The path is encoded by a string only containing 'O' and 'l'. Each character, from left to right, shows whether going left (encoded by '0') or right (encoded by '1') from a node can lead to the target node. For example, we want to find "g" in the following tree (only the "str" components are shown) : // "b" // "E" "g" // The returned string should be "011". (Go left from "a", then go right from "b", and finally go right from "d" can lead us to "g".) If s is in root node, then return an empty string. If s is not in the tree, then return "-1". You can assume that the "str" components of all the nodes are unique in a tree.

Answer 1

I am assuming that structure of node is

class Node{
   string data;
   Node left, right;
   Node(string data){
       this.data = data;
       left = null;
       right = null;
   }
}

std::string findpath(const std::string &s, Node root)
{
   if(root == null)
       return "-1";
   if(root->data == s) // if match then return empty string
       return "";
   string x = findpath(s, root->left);//go to the left subtree
       if(x != "-1")
           return "0" + x;
   x = findpath(s, root->right);//go to the right subtree
       if(x != "-1")
           return "1" + x;
   return "-1";
}