Think of recursive methods.

Write a recursive function that gives a node of the tree and returns S[node].

Call the function above on the root of the tree and get k-th character of it.