How to construct a trie data structure with Objective-C?

Question

Even though Objective-C is a superset of C, I would like to have feedback on how to create a trie data structure with Objective-C. I've started coding the interface, but need some help in understanding how to add Trie nodes (e.g. collection items) for storing words.

@interface Trie : NSMutableArray {
   Trie *child;
   BOOL final;
}

@property(nonatomic, retain)Trie *child;
@property(nonatomic, assign)BOOL final;

-(void)addWord:(NSString *)_word;

@end

Answer 1

I wrote up a quick implementation for you that should be more or less functional, at the very least it can be a starting point. Notice that I got rid of the array subclass. You generally don't want to subclass NSArrays and here you can avoid subclassing in general. See inheritance vs composition.

@interface Trie : NSObject

@property (nonatomic, strong) NSMutableArray *children;
@property (nonatomic, strong) NSString *key;
@property (nonatomic, readonly) BOOL isFinal;

- (void) addWord:(NSString *)word;
- (id) initWithKey:(NSString *)key;

@end

@implementation Trie

// designated initializer, initializes our array of children and sets the key
- (id) initWithKey:(NSString *)key
{
    if(self = [super init])
    {
        _key = key;
        _children = [NSMutableArray new];
    }
    return self;
}

- (void) addWord:(NSString *)word
{
    // no more characters left, this is our base case
    if(! word.length)
    {
       return;
    }

    Trie *childToUse;
    NSString *firstCharacter = [word substringToIndex:1];

    // look for an existing node to dive into
    for(Trie *child in _children)
    {
        if([child.key isEqualToString:firstCharacter])
        {
            childToUse = child;
            break;
        }
    }

    // create a new node if there isn't one
    if(! childToUse)
    {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [_children addObject:childToUse];
    }

    // we now have a node, add the rest of the word into our trie recursively
    [childToUse addWord:[word substringFromIndex:1]];
}

// no actual ivar is stored for this property, its value is returned dynamically by looking at the array count, which can change when more elements are added
- (BOOL) isFinal
{
    if(! _children.count)
    {
        return YES;
    }
    else
    {
        return NO;
    }
}

@end

Just initialize your root node by doing something like [[Trie alloc] initWithKey:@""].

Answer 2

Based off of @Dima's solution, here's a modernized version which uses array type descriptors, block based enumeration, makes children immutable from outside the Trie class, initializes children lazily to save space in the case of leaf nodes, and removes an un-needed member variable.

Trie.h:

@interface Trie : NSObject

@property (nonatomic, strong, readonly) NSMutableArray <Trie *>*children;
@property (nonatomic, strong) NSString *key;

- (id)initWithKey:(NSString *)key;
- (void)addWord:(NSString *)word;
- (BOOL)isLeaf;

@end

Trie.m:

@interface Trie ()

@property (nonatomic, strong, readwrite) NSMutableArray <Trie *>*children;

@end

@implementation Trie

- (id)initWithKey:(NSString *)key
{
    if (self = [super init]) {
        _key = key;
    }

    return self;
}

- (void)addWord:(NSString *)word
{
    if (word.length == 0) {
        return;
    }

    if (!self.children) {
        self.children = [NSMutableArray new];
    }

    NSString *firstCharacter = [word substringToIndex:1];
    __block Trie *childToUse = nil;
    [self.children enumerateObjectsUsingBlock:^(Trie *child, NSUInteger idx, BOOL *stop) {
        if ([child.key isEqualToString:firstCharacter]) {
            childToUse = child;
            *stop = YES;
        }
    }];

    if (!childToUse) {
        childToUse = [[Trie alloc] initWithKey:firstCharacter];
        [self.children addObject:childToUse];
    }

    [childToUse addWord:[word substringFromIndex:1]];
}

- (BOOL)isLeaf
{
    return self.children.count == 0;
}

@end