# More Problems

### Kth Element*

Suppose we have a binary tree where each node contains a character and the same node can appear in more than one place. For example:

```
A
/ \
B B
/ \ / \
C D C D
```

Notice that even though B appears more than once, it is the same node so the subtree rooted at B is the same. Thus, we cannot have B as a parent of B. The following code finds the kth element that appears in a preorder traversal of the tree:

```
class TreeNode {
char val;
TreeNode left;
TreeNode right;
}
public String preorder(TreeNode node) {
if (node == null) {
return "";
}
return node.val + preorder(node.left) + preorder(node.right);
}
public char getk(TreeNode root, int k) {
return preorder(root).charAt(k);
}
```

- What is the worst case time complexity of
`getk`

? - Write a more efficient implementation of
`getk`

.