---
tags: leetcode
---

# [2096. Step-By-Step Directions From a Binary Tree Node to Another](https://leetcode.com/problems/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
<!--
# Test Cases

[5,1,2,3,null,6,4]
3
6

[2,1]
2
1

[MLE](https://leetcode.com/submissions/detail/707420638/testcase/)
-->