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 noden
, the noden
becomes the new leaf node, and can be also counted as leaf). You are given the functionint 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.