0
$\begingroup$

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!

enter image description here

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Apr 26 '18 at 10:27
  • $\begingroup$ 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.) $\endgroup$
    – j_random_hacker
    Apr 26 '18 at 12:25
  • $\begingroup$ It seems you already know a solution to this problem, so I am not sure what more there is to say. $\endgroup$
    – D.W. ♦
    Apr 26 '18 at 13:03
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Apr 26 '18 at 13:22
  • $\begingroup$ @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.. $\endgroup$
    – slomil
    Apr 26 '18 at 13:23
0
$\begingroup$

I would leave a comment but I have less that 50 rep.

So, if I understand the question, DFS (or a way to parse the tree) is inevitable and all you need is an array (one cell for each level, plus one for the leaves) to count how many nodes are on each level. So given the numNodes you can start decrementing from the last (non-zero) element and check which would be the last non-zero element you will reach.

Also you don't actually need a stack, cause it is already implemented from the OS for you. So you just need to use a recursive algorithm passing each time the correct part of the array to the next call to calculate the nodes in the sub-tree. Now, all you need to know is the initial length of the tree. You run again the kind-of the same recursive algorithm but this time you are interested to know the total number of elements in the tree. Then the length of the array would be equal to the length of the total elements in the tree.

Time: O(n)

Space: O(n)

I'm not sure if I can write code here. I hope I was clear :)

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes that's it, thank you!!! i failed to figure that out in the given time (besides 3 more problems) :/// (i only came up with my incorrect solution) i'm a little dumb..:/// $\endgroup$
    – slomil
    Apr 26 '18 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.