# BinaryTree minimum possible height

I have one question for which I don't know any good solution (and my solution doesn't satisfy constraints). Namely, on one of the interviews i got problem like this:

Determine the minimum possible height of the binary tree, if you could remove numNodes leaf nodes from the tree (where after removal of all leaf children of node n, the node n becomes the new leaf node, and can be also counted as leaf). You are given the function int minimumHeight(Node* root, int numNodes), where root is the pointer to the root of the tree, which should be completed, using any oop language.

Constraints are that you can't actually delete node from tree, and you can't use queue or stack, arraylist, list, hashmap, hashset, etc. (you cannot use any built-in c++ stl data structure, you can though make your own from scratch)
My solution used BFS where I stored for each node its level in tree using hashmap m, and created an array arr which contained all nodes, and then sorted it based on node levels in ascending order, and after that the function should return m.get(arr[arr.length-numNodes-2]). (i wrote code in java)
Without constraints I think this could work,but I guess it's not good enough.. Does someone maybe know is there some more elegant way to solve this? (without using unnecessary data structures, and maybe without any sorting) Thank you in advance!

Here if numNodes is 5, the minimum height you could obtain is 2,because first you must delete nodes with 5,11,4 or 2 value,and then you can delete nodes with values 9,6,etc. so in total you will have 5 possibly removed nodes, and 2 will be the minimum height of the tree.

• Your question mentions C++ and STL. However, it seems that these references could be removed. This would make the question more appropriate for this site. – Yuval Filmus Apr 26 '18 at 10:27
• Hint: Is there a way to compute, for each node, the number of nodes that would need to deleted for it to become a leaf? (This would be 0 for nodes that start out as leaves.) – j_random_hacker Apr 26 '18 at 12:25
• It seems you already know a solution to this problem, so I am not sure what more there is to say. – D.W. Apr 26 '18 at 13:03
• Coding questions are off-topic here. Restrictions about STL data structures are not relevant here. You should focus on the algorithm. If you have any requirements on the algorithm, please figure out a way to ask them in a language-independent way; if you can't figure out how to do that, then the question might not be suitable here. – D.W. Apr 26 '18 at 13:22
• @D.W. I think that could be one solution if the interviewer hadn't said that we can't use any stl datastructures..also, when some guy asked him if we could use built-in sorting functions, or is it necessary to implement our own sorting function for the problem, he said that we don't need sorting at all xD maybe I didn't understand him well..i surely don't know how to solve problem with all these constraints.. – slomil Apr 26 '18 at 13:23