Problem statement

https://binarysearch.com/problems/Tree-Traversal/

Solution

Traverse tree and create parents dictionary, then follow instructions.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, root, moves):
        p = {}
        def dfs(node, par):
            p[node] = par
            if node.left: dfs(node.left, node)
            if node.right: dfs(node.right, node)

        dfs(root, None)
        node = root
        for x in moves:
            if x[0] == "R": node = node.right
            if x[0] == "L": node = node.left
            if x[0] == "U": node = p[node]

        return node.val