Skip to content

Instantly share code, notes, and snippets.

@marcinkuptel
Last active August 29, 2015 14:22
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 marcinkuptel/5eb7f125c8521490114f to your computer and use it in GitHub Desktop.
Save marcinkuptel/5eb7f125c8521490114f to your computer and use it in GitHub Desktop.
Method checking whether a binary tree is also a BST
#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