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

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

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:@""].

Many thanks @Dima, looks fantastic! I'll give this a try in Xcode and will let you know if I have any questions. — Wayne Bishop, Apr 09 '14 at 22:33
Sure! I also just added a base case which I forgot to do earlier. Without this, you would end up with a `NSRangeException` after your whole word has been added. — Dima, Apr 09 '14 at 22:43
Hi @Dima, in your example, how is the "key" used? Is this the actual character that will be associated with each node? Why don't we store key information in the NSMutableArray? — Wayne Bishop, Apr 09 '14 at 23:35
Each node stores its own key and each key is indeed just a single character. The array is a list of the children nodes which each have their own key. You can modify this if you'd like to store the full string each node represents or whatever other data you'd like to see, it's basically arbitrary. Does that make sense? — Dima, Apr 09 '14 at 23:53
Hi @Dima, thanks a lot its a good start point for me. Just one question - why do you need to initialize the Trie with a key, and after that set the key again in this line: `childToUse.key = firstCharacter;`? Thanks again. — goldengil, May 12 '14 at 15:16
@goldengil good catch! That second setter call is totally unnecessary. I think I refactored this solution before I submitted it and forgot to get rid of that bit. I'll do that now. — Dima, May 12 '14 at 17:59

awolf · Answer 2 · 2015-09-30T20:55:15.587

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

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

2 Answers2