Last active
August 29, 2015 14:22
-
-
Save marcinkuptel/5eb7f125c8521490114f to your computer and use it in GitHub Desktop.
Method checking whether a binary tree is also a BST
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#import <Foundation/Foundation.h> | |
@interface Node: NSObject | |
@property (nonatomic, readonly, assign) int key; | |
@property (nonatomic, readonly, strong) id value; | |
@property (nonatomic, strong) Node *left; | |
@property (nonatomic, strong) Node *right; | |
+ (Node*) nodeWithKey: (int) key value: (id) value; | |
+ (BOOL) isBinarySearchTree: (Node*) tree; | |
- (instancetype) initWithKey: (int) key value: (id) value; | |
@end | |
@implementation Node | |
+ (Node*) nodeWithKey:(int)key value:(id)value { | |
return [[Node alloc] initWithKey: key value: value]; | |
} | |
+ (BOOL) isBinarySearchTree: (Node*) tree | |
{ | |
if(tree == nil) return NO; | |
return [self check: tree leftBoundary: INT_MIN rightBoundary: INT_MAX]; | |
} | |
+ (BOOL) check: (Node*) node leftBoundary: (int) left rightBoundary: (int) right | |
{ | |
if(node == nil) return YES; | |
BOOL leftSubtree = [self check: node.left leftBoundary: left rightBoundary: node.key]; | |
BOOL rightSubtree = [self check: node.right leftBoundary: node.key rightBoundary: right]; | |
return leftSubtree && rightSubtree && (node.key >= left) && (node.key <= right); | |
} | |
- (instancetype) initWithKey:(int)key value:(id)value { | |
self = [super init]; | |
if(self) { | |
_key = key; | |
_value = value; | |
} | |
return self; | |
} | |
@end | |
int main(int argc, char *argv[]) { | |
@autoreleasepool { | |
Node *objectiveC = [Node nodeWithKey: 10 value: @"objectiveC"]; | |
Node *go = [Node nodeWithKey: 2 value: @"go"]; | |
Node *python = [Node nodeWithKey: 6 value: @"python"]; | |
Node *cpp= [Node nodeWithKey: 3 value: @"cpp"]; | |
Node *java = [Node nodeWithKey: 4 value: @"java"]; | |
python.left = cpp; | |
python.right = objectiveC; | |
cpp.left = go; | |
cpp.right = java; | |
NSLog(@"Tree is BST: %i", [Node isBinarySearchTree: python]); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment