Tree Traversal via Blocks with a premature stopping condition

Question

I'm doing In-Order traversal of a Binary tree with a certain method executed on each node. I do this using a inOrderTraversalWithOperation: method as shown below that uses a Block to define the function that is needed at each node.

-(void) inOrderTraversalWithOperation:(void (^) (BinaryTreeNode *))operation
{
    [self.leftChild inOrderTraversalWithOperation:operation];
    if (operation)
    {
        operation(self);
    }
    [self.rightChild inOrderTraversalWithOperation:operation];

}

Suppose I want to stop when the Block execution hits a certain condition. One way to do it is to make the inOrderTraversalWithOperation: return a BOOL, and make the Block return a BOOL, as shown below.

But I am wondering if I can do it using the BOOL *stop approach used by Apple in many of its APIs. How do the Blocks with that flag work "underneath"?

-(BOOL) inOrderTraversalWithStopOperation:(BOOL (^) (BinaryTreeNode *))operation
{
    BOOL shouldStop = NO;

    shouldStop = [self.leftChild inOrderTraversalWithStopOperation:operation];
    if (operation !=nil && shouldStop == NO)
    {
        shouldStop = operation(self);
    }

    if (!shouldStop)
    {
        shouldStop = [self.rightChild inOrderTraversalWithStopOperation:operation];
    }

    return shouldStop;
}

EDIT Based on Josh's comment it looks like BOOL *stop will allow this but I still need inOrderTraversalWithStopOperation: to return a BOOL

-(BOOL) inOrderTraversalWithStopOperation:(void (^) (BinaryTreeNode *, BOOL *))operation
{
    BOOL shouldStop = NO;

    shouldStop = [self.leftChild inOrderTraversalWithStopOperation:operation];
    if (operation !=nil && shouldStop == NO)
    {
        operation(self, &shouldStop);
    }

    if (!shouldStop)
    {
        shouldStop = [self.rightChild inOrderTraversalWithStopOperation:operation];
    }

    return shouldStop;
}

score 1 · Accepted Answer · edited May 23 '17 at 11:48

The "stop" argument to an enumeration Block is just like any other indirect return value: you're passing an address from one scope so that the next scope can put something there. That something is then available in the original scope.

To add a stop flag to your operation type, you'd change its signature

typedef void (^NodeOperation)(BinaryTreeNode *, BOOL *);

In the calling context of the Block, you do what you've already done: create a BOOL for this flag and set it to NO. Then you pass its address in to the Block: operation(self, &stop);.

Inside the operation, you set the flag if necessary by dereferencing it and assigning a value: *stop = YES; (it would be a good idea to check that it's not NULL first; dereferencing NULL is illegal).

Back in the controlling scope, do what you're already doing: check the flag after each operation and decide what to do.

There's code samples for this mechanism in my related answer to What is the BOOL *stop argument for enumerateObjectsUsingBlock: used for?

To control the recursive method invocations, you have to pass information back somehow. You can do that most easily with the direct return value. The other option (although I don't think it buys you anything in this case) would be to add a BOOL pointer parameter to the method; then you can just keep passing around that same reference to every level. (That would probably mean creating a helper method so that the original caller doesn't have to worry about that argument.)

Thanks Josh. I can clearly see how to know if block results in a STOP condition at current node. What I can't get is how to know a STOP condition was met when the method is called on Left child and right child. It looks like we need the "traversal method" to return a BOOL. I.e the BOOL *stop will only help in eliminating the BOOL return type of the completion block argument of the method, but we still need the method's return type to be BOOL. Is that correct? See my edited question above. — Smart Home, Oct 16 '16 at 01:36
Right, any given invocation wouldn't be able to affect previous invocations without passing information back with the direct return. Or, if you wanted to -- I don't think it would buy you anything here -- you could add a `BOOL *` argument to the method as well, and pass the original `BOOL` in the same way to each method invocation (i.e., `[self.leftChild inOrderTraversalWithStop:&shouldStop operation:operation]` or similar). That would probably mean creating a helper method to avoid making the original caller have to pass in the boolean pointer. — jscs, Oct 16 '16 at 02:11
Thanks, can you add this your answer so that I can accept it? — Smart Home, Oct 16 '16 at 02:25

Tree Traversal via Blocks with a premature stopping condition

1 Answers1