Skip to content

Instantly share code, notes, and snippets.

@kmdarshan
Created March 21, 2015 22:08
Show Gist options
  • Save kmdarshan/ab8ccdb0640f252a0528 to your computer and use it in GitHub Desktop.
Save kmdarshan/ab8ccdb0640f252a0528 to your computer and use it in GitHub Desktop.
Insertion and deletion into a binary search tree in objective c
#import
@interface Node : NSObject{
Node *left;
Node *right;
NSObject *data;
}
@property (nonatomic, strong) Node *left;
@property (nonatomic, strong) Node *right;
@property (nonatomic, strong) NSObject *data;
@end
#import "Node.h"
@implementation Node
@synthesize left;
@synthesize right;
@synthesize data;
@end
-(Node*) insertNode:(Node*) root forObject:(NSObject*)data{
Node *cur = root;
Node *prev = NULL, *temp;
temp = [[Node alloc] init];
temp.data = data;
temp.left = temp.right = NULL;
if(root == NULL){
root = temp;
}else{
// iterate through the nodes
NSString *valStr = (NSString*) data;
NSInteger val = [valStr intValue];
while (cur != NULL) {
prev = cur;
NSString *valStr2 = (NSString*) cur.data;
cur = (val < [valStr2 intValue]) ? cur.left: cur.right;
}
NSString *valStr2 = (NSString*)prev.data;
if(val < [valStr2 intValue]){
prev.left = temp;
}else{
prev.right = temp;
}
}
return root;
}
-(Node*) deleteNode:(Node*) root forValue:(NSObject*) value{
if (root == NULL) {
return root;
}
Node *curr = root;
Node *parent;
int val = [(NSString*)value intValue];
while (curr != NULL && val != [(NSString*)curr.data intValue]) {
parent = curr;
curr = (val < [(NSString*)curr.data intValue]) ? curr.left : curr.right;
}
if (curr == NULL) {
NSLog(@"item not found");
return root;
}
Node *q, *suc;
if (curr.left == NULL) {
q = curr.right;
}else if (curr.right == NULL){
q = curr.left;
}else{
// obtain in order successor
suc = curr.right;
while (suc.left != NULL) {
suc = suc.left;
}
suc.left = curr.left;
q = curr.right;
}
if (parent == NULL) {
return q;
}
if (curr == parent.left) {
parent.left = q;
}else{
parent.right = q;
}
curr = NULL;
return root;
}
-(void) displayInorder:(Node*)root{
if(root != NULL){
[self displayInorder:root.left];
NSLog(@"%@ ", root.data);
[self displayInorder:root.right];
}
}
// from your main program
- (void) main
{
[super viewDidLoad];
Node *root = NULL;
NSArray *array = [[NSArray alloc] initWithObjects:@"100",@"1", @"99", @"23", @"13", nil];
for (NSObject *val in array) {
root = [self insertNode:root forObject:val];
}
[self deleteNode:root forValue:@"23"];
[self displayInorder:root];
return;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment