I have a binary tree where each node can have a value.
I want to find the node in the tree that has value null and is closest to the root. If there are two nodes with the same distance from the root, either will do. I need to minimize the number of read accesses to the binary tree. Assume that working memory is limited to just k nodes.
DFS to depth k is exhaustive but will not find the closest node unless I run through the whole tree first. BFS will find the closest, but it might fail because DFS can find deeper nulls with the same memory.
I'd like to have the fewest number of read accesses to the tree and find the closest null node.
(I'll need to implement this in n-way trees eventually, too, so a general solution would be good. No write access to the tree, just read.)