Directions Through a Tree

Medium

You are given the root of a binary tree with n nodes, all with distinct values. You also get the values of two different nodes of this tree, start and finish. Describe the shortest path from node start to node finish as a string of letters: - 'L' means go to the left child; - 'R' means go to the right child; - 'U' means go up to the parent. Return that string.

Example 1

root=tree_node([4, 2, 6, 1, 3, 5]), start=3, finish=5 → 'UURL'

The path is 3 → 2 → 4 → 6 → 5: two steps up, then right and left.

Example 2

root=tree_node([1, None, 2]), start=1, finish=2 → 'R'

Node 2 is the right child of the root.

Example 3

root=tree_node([3, 1, 2]), start=2, finish=3 → 'U'

Constraints

2 ≤ n ≤ 10⁵
1 ≤ node value ≤ 10⁵, all values distinct
Both start and finish are nodes of the tree
start ≠ finish

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search String Binary Tree

Similar problems

Tree From Bracket Notation Medium Tree in Compact Brackets Medium Smallest Leaf-to-Root Word Medium Routes from Root to Leaves Easy Tree From a Dashed Preorder Record Hard

Input

root=tree_node([4, 2, 6, 1, 3, 5]), start=3, finish=5

Expected

'UURL'

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.