1
class Solution {
2
 public:
3
  bool search(TreeNode *root, int target, string &s) {
4
    if (root == NULL) {
5
      return false;
6
    }
7
    if (root->val == target) {
8
      return true;
9
    }
10

11
    bool find1 = search(root->left, target, s += 'L'); // search on left side
12
    if (find1) return true;
13
    s.pop_back(); // backtracking step
14

15
    bool find2 = search(root->right, target, s += 'R'); // search on right side
16
    if (find2) return true;
17
    s.pop_back(); // backtracking step
18
    return false;
19
  }
20

21
  TreeNode *lca(TreeNode *root, int n1, int n2) {
22
    if (root == NULL) return NULL;
23
    if (root->val == n1 or root->val == n2) return root;
24

25
    TreeNode *left = lca(root->left, n1, n2);
26
    TreeNode *right = lca(root->right, n1, n2);
27

28
    if (left != NULL && right != NULL) return root;
29
    if (left) return left;
30
    if (right) return right;
31

32
    return NULL; // not present in tree
33
  }
34
  string getDirections(TreeNode *root, int startValue, int destValue) {
35
    TreeNode *temp = lca(root, startValue, destValue);
36

37
    string s1, s2;
38
    search(temp, startValue, s1);
39
    search(temp, destValue, s2);
40
    for (auto &it : s1) {
41
      it = 'U';
42
    }
43
    return s1 + s2;
44
  }
45
};