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: 
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