# 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);
}

1. What is the worst case time complexity of getk?
2. Write a more efficient implementation of getk.