February 10, 2016 Andrey

Coding question print binary tree by level in Objective C

This question was previously asked on the Facebook interview.
Given input as a binary tree print to console each level followed by new line character.
Input: Tree
Output:
“A\n
BC\n
DEF”

Solution: Do a breadth first search algorithm on a graph which will go over an entire tree and will build a resulted string.
First of all let’s create a custom class Node:

@interface Node : NSObject

@property NSObject *left;
@property NSObject *right;
@property NSString *value;

@end

Second let’s extend NSMutableArray with our own queue methods:

@interface  NSMutableArray (QueueAdditions)
- (id) dequeue;
- (void) enqueue: (id)obj;
@end

@implementation  NSMutableArray (QueueAdditions)

- (id) dequeue {
    id headObject = [self objectAtIndex:0];
    if (headObject != nil) {
        [self removeObjectAtIndex:0];
    }
    return headObject;
}

- (void) enqueue:(id)obj{
    [self addObject:obj];
}
@end

Add the function that will traverse over the graph and will build a resulted string:

+(NSString*) printTree:(Node*)node{
    
    if (node == nil){
        return @"";
    }
    
    NSMutableString *result = [[NSMutableString alloc] init];
    NSMutableArray *queue = [[NSMutableArray alloc] init];
    [queue enqueue:node];
    [queue enqueue:[NSNull null]];
    while (true){
        Node *curObject = [queue dequeue];
        if ([curObject isEqual:[NSNull null]]){
            [result appendString:@"\n"];
            
            if ([queue count] == 0){
                break;
            }
            [queue addObject:[NSNull null]];
            continue;
        }
        [result appendString:curObject.value];
        
        if (curObject.left){
            [queue enqueue:curObject.left];
        }
        if (curObject.right){
            [queue enqueue:curObject.right];
        }
    }
    
    return result;
}

code at gitlab: https://github.com/svetdev/print-tree-by-level