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
numNodesleaf nodes from the tree (where after removal of all leaf children of node
n, the node
nbecomes 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.