Google L4 Phone Screen Round (US)

Given 2 numbers and an unsorted binary tree, find the path between them and return it as a string with the words "up", "right" and "left"

       1
     /  \
    2    7 
   / \
  8   6
 /
5

Path(root, 6, 7) -> "up, up, right"
Path(root, 7, 8) -> "up, left, left"
Path(root, 5, 6) -> "up, up, left"

I asked the following questions:

• are the node values unique? Yes
• Will both nodes be always present in tree? Yes

Solved it using the following approach:

1. Find LCA node between the two nodes.
2. A path function that will record L/R from LCA node to first node.
3. Same path function that will record L/R from LCA node to second node.
4. Form the answer string a. place all "up" strings for path from LCA to start node b. append the recorded path from LCA to end node

Interviewer asked if I can optimise and decrease the traversals, as I was traversing the tree thrice. But couldn't think well in that interview setting.

EDIT: Cleared the phone screen round. Moving Onward