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

---

My Solution

The Key Idea for Solving This Coding Question

C++ 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) {}
 * };
 */
 
 #define START (true)
 
class Solution {
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        TreeNode *lca = findLCA(root, startValue, destValue);
        
        string path1, path2;
        findPath(lca, path1, startValue, START);
        findPath(lca, path2, destValue, !START);
        
        return path1 + path2;
    }
    
private:
    TreeNode *findLCA(TreeNode* root, int startValue, int destValue) {
        if (!root) {
            return nullptr;
        }
        
        if (root->val == startValue || root->val == destValue) {
            return root;
        }
        
        TreeNode *leftSubtree = findLCA(root->left, startValue, destValue);
        TreeNode *rightSubtree = findLCA(root->right, startValue, destValue);
        if (!leftSubtree) {
            return rightSubtree;
        }
        if (!rightSubtree) {
            return leftSubtree;
        }
        
        return root;
    }
    
    TreeNode *findPath(TreeNode* root, string &path, int value, bool flag) {
        if (!root) {
            return nullptr;
        }
        
        if (root->val == value) {
            return root;
        }
        
        if (flag == START) {
            path.push_back('U');
        } else {
            path.push_back('L');
        }
        
        TreeNode *leftSubtree = findPath(root->left, path, value, flag);
        if (!leftSubtree) {
            path.pop_back();
        } else {
            return leftSubtree;
        }
        
        if (flag == START) {
            path.push_back('U');
        } else {
            path.push_back('R');
        }
        
        TreeNode *rightSubtree = findPath(root->right, path, value, flag);
        if (!rightSubtree) {
            path.pop_back();
        } else {
            return rightSubtree;
        }
        
        return nullptr;
    }
};

Time Complexity

Space Complexity

Miscellane