views:

321

answers:

4

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

+1  A: 

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.

Douglas Leeder
+2  A: 

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.

Nick D
+2  A: 

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.

Geerad
I wonder if there is a good order for optimizing the IDDFS? For instance, if my memory is 4 nodes and the tree is binary, after reading nodes 0,1,2,3, I can now read nodes 4,5,6 without starting over because I have already read 0,1,2. Now if I have 0,1,2,6 in memory I can read 7 without having to re-read 0,2,etc.Have to draw it out for it to make sense...
Eyal
I'm not sure if I understand you correctly, but you would have to use memory to keep track of the fact that you read those nodes, so you'd end up no better than BFS.
Geerad
@Geerad: IDDFS need lessor memory then BFS -- you don't need an explicit queue for DFS.
J-16 SDiZ
A: 

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.

Geerad