Step-By-Step Directions From a Binary Tree Node to Another

Leetcode Problem:

• Step-By-Step Directions From a Binary Tree Node to Another

Summary

• This problem requires finding the shortest path from a start node to a destination node in a binary tree
• The path is represented as a string of 'L', 'R', and 'U' characters, where 'L' represents going to the left child, 'R' represents going to the right child, and 'U' represents going to the parent node.

Approach

• This solution uses a depth-first search approach to find the shortest path from the start node to the destination node
• It first searches for the start node and stores its path in the rootToStart vector
• Then, it searches for the destination node and stores its path in the rootToDest vector
• Finally, it constructs the shortest path by concatenating the 'U' characters to the start of the path and the 'L' and 'R' characters to the end of the path.

Complexity

• The time complexity of this solution is O(n), where n is the number of nodes in the tree
• This is because each node is visited once during the depth-first search
• The space complexity is also O(n) due to the storage of the paths in the rootToStart and rootToDest vectors.

Explain

• The solution uses two vectors, rootToStart and rootToDest, to store the paths from the start node to the destination node
• The searchPath function is used to search for the start node and the destination node, and it uses a depth-first search approach to traverse the tree
• The getDirections function is used to construct the shortest path by concatenating the 'U' characters to the start of the path and the 'L' and 'R' characters to the end of the path.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

vector rootToStart;
vector rootToDest;
vector rootToDestChar;
class Solution {
public:
    bool searchPath(TreeNode* ptr, int dest, vector &path){
        if (ptr == nullptr) return false;
        if (ptr->val == dest) {
            path.push_back(dest);
            return true;
        }
        path.push_back(ptr->val);
        rootToDestChar.push_back('L');
        if (searchPath(ptr->left, dest, path)){
            return true;
        }
        rootToDestChar.pop_back();
        rootToDestChar.push_back('R');
        if (searchPath(ptr->right, dest, path)){
            return true;
        }
        rootToDestChar.pop_back();
        path.pop_back();
        return false;
    }
    string getDirections(TreeNode* root, int startValue, int destValue) {
        rootToStart.clear();
        rootToDest.clear();
        searchPath(root, startValue, rootToStart);
        rootToDestChar.clear();
        searchPath(root, destValue, rootToDest);
        
        string res = "";
        int cnt = 0;
        while(cnt < rootToStart.size() && cnt < rootToDest.size() && rootToStart[cnt] == rootToDest[cnt]) cnt++;
        for(int i = 0; i < rootToStart.size() - cnt; i++){
            res += "U";
        }
        for(int i = cnt-1 ; i < rootToDestChar.size(); i++){
            res += rootToDestChar[i];
        }
        return res;
    }
};