Submitted by matt_eaton
on Sun, 11/25/2018 - 09:52 PM
Tree data structures are a fundamental data structure used in computer science. Tree's can be used for searching and sorting data hierarchies such as UIView's via tags and custom objects via leveling order. Binary tree's are also very similar in that they provide an efficient sorting mechanism to quickly search large amounts of data. A while back I was looking through some of my old Objective-C archives and found a binary tree implementation that was created but never seen the light of day on any project. To get some use out of this code and to share my binary tree implementation I thought I would write a brief tutorial on how this data structure created in Objective-C. First, before getting started, there are a few things to keep in mind about this tutorial; the first is that this tutorial was created as a macOS command line application in Mojave, but any recent version of Xcode or macOS should work with this sample code. The next is this tutorial does require a bit of knowledge in Objective-C either and Computer Science, but nothing too deep. Let's jump in!
Creating a Binary Tree in Objective-C 🚀
First, before I dive into the code, let me provide a brief explanation of how binary tree's are created. A binary tree data structures work with the idea that each parent node can have a left and right node only. The left node is considered to be less than the parent node and the right node is considered to be the greater than the parent node. Using these rules, a binary tree is created by recursively attaching a left and right node to a parent by evaluating in this case the numeric value. Once the tree is then created, a numeric value can then be obtained through searching the tree in the same recursive way.
To get started the first thing that is needed is a node object. In objective-c the node object is an NSObject that looks something like this:
#import <Foundation/Foundation.h> NS_ASSUME_NONNULL_BEGIN @interface Node : NSObject @property int num; @property Node *left; @property Node *right; - (id)initWithValue:(int)value; @end NS_ASSUME_NONNULL_END @implementation Node - (id)initWithValue:(int)value { self = [super init]; if (self != nil) { self.num = value; self.left = NULL; self.right = NULL; } return self; } @end
The node object has a left and right reference and a num value to hold the data present for the object. Notice that each left and right reference is also a node type that will allow the tree to continue growing by reference horizontally. Next notice the constructor on the node object. This can be used to assign the num value and assign NULL to both the left and right nodes when a new node is added to the tree.
Next, let's take a look at the BinaryTree object. The BinaryTree object is setup to encompassed all of the methods and data associated with the data structure. First, let's look at the createBinaryTree: method. This method takes the root node and an array of data passed in. Using the root node, the array is looped and the insertNode: method is called to add the numeric value at either the left or the right side of each of the parent nodes. Each time a new node is added, the constructor from the node object is called and the node is recursively added to the tree.
#import <Foundation/Foundation.h> #include "Node.h" NS_ASSUME_NONNULL_BEGIN @interface BinaryTree : NSObject - (Node *) insertNode: (Node *)node withData:(int)value; - (Node *) createBinaryTree:(NSArray *)treeData andRoot:(Node *)root; - (void) printBinaryTree: (Node *)node; - (int) find:(int)value atLevel:(int)level onTree:(Node *)tree; @end NS_ASSUME_NONNULL_END @implementation BinaryTree - (Node *) insertNode: (Node *)node withData:(int)value { if (node == NULL) { Node *newNode = [[Node alloc] initWithValue: value]; return newNode; } else { // @[@5, @6, @17, @1, @15, @32, @3, @8, @91]; if (value <= node.num) { node.left = [self insertNode: node.left withData: value]; } else { node.right = [self insertNode: node.right withData: value]; } return node; } } - (Node *) createBinaryTree:(NSArray *)binaryTreeRawData andRoot:(Node *)root { // Complexities of creating a binary tree. // Time complexity: O(n * log(n)) // * at least one full interation of the array to build the tree, so (n) up front. // Space complexity: O(n) // Set as the root node on the tree root.num = [[binaryTreeRawData objectAtIndex:0] intValue]; int i = 1; while (i < (int)[binaryTreeRawData count]) { root = [self insertNode: root withData: [[binaryTreeRawData objectAtIndex:i] intValue]]; i++; } return root; } @end
After the binary tree is completely built the root node can be passed into the printBinaryTree method: to recursively print out each num value on a node. Looking at the output from this method you will see that the data is now in order from least to greatest.
- (void) printBinaryTree: (Node *)node { if (node == NULL) { return; } [self printBinaryTree: node.left]; NSLog(@"Number %d", node.num); [self printBinaryTree: node.right]; }
Finally, here is the main that creates the binary tree. First notice that the root node and binary tree objects are created. The root will be used as a starting point for the data structure. The tree object will be used as an instance of the binary tree data structure and the root is then passed into the createBinaryTree: method with an array of numeric data. Lastly the printBinaryTree: method is called and the tree is printed out as shown above.
#import <Foundation/Foundation.h> #include "BinaryTree.h" int main(int argc, const char * argv[]) { @autoreleasepool { NSArray *binaryTreeRawData = @[@5, @6, @17, @1, @15, @32, @3, @8, @91]; Node *root = [[Node alloc] init]; BinaryTree *tree = [[BinaryTree alloc] init]; root = [tree createBinaryTree:binaryTreeRawData andRoot:root]; [tree printBinaryTree:root]; } return 0; }
In Summary ⌛️
In summary I hope that this tutorial provides more information on binary trees and how to create them in Objective-C. This example is a bit different than some implementations out there because of the Objective-C APIs used, but the base concepts are still present. I hope you enjoyed this tutorial and if you have any questions, comments, or concerns, please leave a comment below and I will make sure to address it as soon as I am able to. Thank you very much for reading and the code from this tutorial can be downloaded from my Github here.
Credits: Cover image designed by Freepik.
Member for
3 years 9 monthsLong time mobile team lead with a love for network engineering, security, IoT, oss, writing, wireless, and mobile. Avid runner and determined health nut living in the greater Chicagoland area.