Directions From a Binary Tree Node to Another: Memory Limit Exceeded

There is more than one issue here.

• direct may get into an infinite recursion problem, because the last recursive call is made without first checking if that would lead to the previously visited node. You did this correctly for going to the left or the right child, but when going to the parent, you didn't do this check. It should be:

  if (parent[root] != prev) 
  {
      direct(parent[root],destValue,root, path+"U");
  }
  

  With this bugfix the code will pass many more test cases, as long as enough memory is available.

• But, even if you fix the previous bug, the memory usage will still be too much. There are testcases with trees of 100K nodes, and which are skewed, so that each node has at the most one child, giving it a height that is also near 100K. By consequence the recursion depth can also become 100K. And at each recursive call a new string (path) is created that gets longer and longer... meaning the combined space needed for those path strings is O(n²) and combined with the stack space we get a space complexity of O(n³) in that case. For n equal to 100K this becomes too big for the memory available on the testing platform.

This second issue can be solved by taking the following actions -- staying as close as possible to your original code:

• Don't use the path parameter, so to avoid creating that many strings.
• Make the function return a boolean to indicate that the destination has been found. When a recursive call returns true, the caller should not have to continue the search with an other recursive call.
• Only start building the path once the destination is found, adding a direction to the path while returning from the recursive calls -- so in reverse order. Your global variable can be used to collect this path. This way only one string is built, not many, and it is extended character by character with the += assignment operator.
• In the main program, reverse this string before returning it.

Here is your code with those changes:

    bool direct(TreeNode* root, int destValue, TreeNode *prev) // No path parameter, return boolean
    {
        if(root==NULL )
        {
            return false;
        }
        if(root->val == destValue)
        {
            global = ""; // Start building a path from the end
            return true; // Indicate that destination was found
        }
        if(root->left!=prev)
        {
            if (direct(root->left,destValue, root)) { // Use the returned boolean
                global += "L"; // Append in which direction we found the destination
                return true; // ... and indicate success
            }
        }
      
        if(root->right!=prev)
        {
            if (direct(root->right,destValue, root)) {
                global += "R";
                return true;
            }
        }
        
        if(parent[root]!=prev) // Don't go back up when we just had come down
        {
            if (direct(parent[root],destValue, root)) {
                global += "U";
                return true;
            }
        }
        return false; // Didn't find the destination in this subtree
   }
    
    
    string getDirections(TreeNode* root, int startValue, int destValue)
    { 
        parent[root]= NULL;
        trav(root, startValue);
        direct(start,destValue, NULL);
        reverse(begin(global), end(global)); // Reverse the path
        parent.clear();
        return global;
    }

More efficiency

There are algorithms where you don't need to have this parent map. They only need one traversal of the tree and will therefore do the job faster in most cases.

Hint: Imagine you know the two downward paths from the root to both nodes, how could you use that information to return the result?