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.