I love posting things to the internet that end up being wrong :).

I think this is an interesting look at ambiguity in wording for computer science terminology. In my mind, height or highest always means node height. The term largest should be reserved for numerical measurement. See the next paragraph for a good example.

Correct me if I'm wrong, but the k highest interpretation with an unsorted tree sounds like a simpler problem. If the tree is unsorted, you must traverse the entire tree, sort the result, and then you have your answer. The more challenging problem sounds to me to be what happens when the tree is already sorted. Interestingly, I think the solution for this problem makes my point better than the original problem. Look at how buildHeights breaks the sub problems down. The height (size) of a value in a node at a given level (height) is a function of the heights (sizes) of sub-trees. I included a main method, so you can run the code and not mentally parse it :). What's interesting to me is the commonality in structure between the two solutions despite the problems asking for radically different things.

Note, I probably could not have come up with this solution in the amount of time allotted in an interview because it took a while to find a solution that properly showed problem decomposition.

  import qualified Data.Map as Map

  data Tree a = Tree a (Maybe (Tree a)) (Maybe (Tree a)) deriving Show

  buildHeights :: Tree a -> Map.Map Int a

  buildHeights (Tree a Nothing Nothing) = Map.singleton 1 a

  buildHeights (Tree a (Just l) Nothing) =
    Map.insert 1 a lRes
    where
      lRes = Map.mapKeys (+1) (buildHeights l)

  buildHeights (Tree a (Just l) (Just r)) =
    Map.unions [rRes, lRes, curRes]
    where
      rRes = (buildHeights r)
      maxRight = maximum $ Map.keys rRes
      lRes = Map.mapKeys (+ (1 + maxRight)) (buildHeights l)
      curRes = Map.singleton (1 + maxRight) a

  kHighest :: Int -> Tree a -> Maybe a
  kHighest k t = (buildHeights t) Map.!? k

  main = do
    let tree = (Tree 4
           (Just (Tree 2
                (Just (Tree 1 Nothing Nothing))
                (Just (Tree 3 Nothing Nothing))))
           (Just (Tree 6
                (Just (Tree 5 Nothing Nothing))
                (Just (Tree 7 Nothing Nothing)))))
      in do {
      putStrLn $ show $ kHighest 1 tree ;
      putStrLn $ show $ kHighest 2 tree ;
      putStrLn $ show $ kHighest 3 tree ;
      putStrLn $ show $ kHighest 4 tree ;
      putStrLn $ show $ kHighest 5 tree ;
      putStrLn $ show $ kHighest 6 tree ;
      putStrLn $ show $ kHighest 7 tree ;
      putStrLn $ show $ kHighest 8 tree ;
         }