Find first null in binary tree with limited memory

Question

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.)

Answer 1

You may want to look at Iterative-deepening depth-first search. It will find the closest node automatically but will be able to reach the same depth as DFS. It will use more read accesses though.

You could also start with BFS, and if you don't find a null with the allowed memory, run DFS.

Answer 2

I would implement a DFS with a simple tree pruning. So, it's not true that you have to run the whole tree.

For example if you have located a null value at height h, you can skip nodes that are in the same or deeper position.

Answer 3

If you can't change the data structure then you'll have to read each node - breadth-first.

If you can change the data-structure, then each node could record the relative depth of the first null child node. (Each to work out from its children's equivalent values).

Then you know which line in the tree to chase down when looking for the earliest null.

Answer 4

There is a simple way, if you're willing to store your tree in an array. Rather than each node having pointers to its left and right children, the children of node n are 2n + 1 and 2n + 2 in the array. (And node n's parent is (n-1)/2, if n != 0.)

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

Simply iterating through the array linearly is equivalent to a BFS, but with space requirements of O(1).

This can easily be extended to n-ary trees. e.g., in a ternary tree, the left child is 3n+1, center is 3n+2, right is 3n+3, and parent is (n-1)/3 if n !=0.