Skip to content

Instantly share code, notes, and snippets.

@kmdarshan
Last active August 29, 2015 14:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kmdarshan/b9f962c5a41bdc09ba0b to your computer and use it in GitHub Desktop.
Save kmdarshan/b9f962c5a41bdc09ba0b to your computer and use it in GitHub Desktop.
Printing level tree order in objective c
//
// Tree.h
// learnObjectiveC
//
// Created by kmd on 3/3/15.
// Copyright (c) 2015 Happy Days. All rights reserved.
//
#import <Foundation/Foundation.h>
@interface TNode : NSObject
{
}
@property (nonatomic, strong) TNode *rlink;
@property (nonatomic, strong) TNode *llink;
@property (nonatomic, assign) NSInteger data;
@end
@interface Tree : NSObject
-(TNode*) insertNode:(NSInteger) value withRootNode:(TNode*) node;
-(void) displayTree:(TNode*) rootNode;
-(void) printLevelTree:(TNode*) node;
@end
//
// Tree.m
// learnObjectiveC
//
// Created by kmd on 3/3/15.
// Copyright (c) 2015 Happy Days. All rights reserved.
//
#import "Tree.h"
#import "RRQueue.h"
@implementation TNode
@end
@implementation Tree
-(TNode*) insertNode:(NSInteger) value withRootNode:(TNode*) node{
if (node == nil) {
node = [TNode new];
node.rlink = nil;
node.llink = nil;
node.data = value;
return node;
} else {
if (value >= node.data) {
node.rlink = [self insertNode:value withRootNode:node.rlink];
} else {
node.llink = [self insertNode:value withRootNode:node.llink];
}
return node;
}
}
-(void) displayTree:(TNode*) rootNode {
if (rootNode!=nil) {
[self displayTree:rootNode.llink];
NSLog(@"%lu", rootNode.data);
[self displayTree:rootNode.rlink];
}
}
-(void)printLevelTree:(TNode *)node {
if (node == nil) {
NSLog(@"empty tree to print");
} else {
// need to print it one by one using a queue
RRQueue *q = [[RRQueue alloc] init];
TNode *tempNode = node;
while (tempNode != nil) {
NSLog(@"%ld", (long)tempNode.data);
if (tempNode.llink != nil) {
[q enQueue:tempNode.llink];
}
if (tempNode.rlink != nil) {
[q enQueue:tempNode.rlink];
}
tempNode = (TNode*)[q deQueue];
}
}
}
-(BOOL) isBinarySearchTree:(TNode*)node {
if (node == nil) {
return YES;
}
if (node.llink != nil && (node.llink.data > node.data ? YES : NO)) {
return false;
}
if (node.rlink != nil && (node.rlink.data < node.data ? YES : NO)) {
return false;
}
if (![self isBinarySearchTree:node.llink] || ![self isBinarySearchTree:node.rlink]) {
return NO;
}
return YES;
}
@end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment