Created
October 21, 2011 21:45
-
-
Save johnstorm/1305065 to your computer and use it in GitHub Desktop.
A single line implementation of checking if a tree is sorted.
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
#include <stdio.h> | |
#include <limits.h> | |
// A macro to return a string of word true or false based on the evaluation given. | |
#define boolToString(_bool_) ((_bool_) ? "true" : "false") | |
// A very simple tree | |
typedef struct _TreeNode | |
{ | |
struct _TreeNode *left; | |
struct _TreeNode *right; | |
int value; | |
} TreeNode; | |
// When calling this function, you should send a reference to an integer who's value is INT_MIN. If you send an invalid pointer a crash should be expected. | |
int isTreeSorted(TreeNode *node, int *previous) | |
{ | |
return node == NULL || (isTreeSorted(node->left, previous) && (*previous <= node->value) && ((*previous = node->value) || 1) && isTreeSorted(node->right, previous)); | |
} | |
int main(void) | |
{ | |
int desiredAnswer = 1; | |
// Build the tree | |
TreeNode l11 = {NULL, NULL, 1}; | |
TreeNode l12 = {NULL, NULL, desiredAnswer ? 7 : 15}; | |
TreeNode l1 = {&l11, &l12, 5}; | |
TreeNode r1 = {NULL, NULL, 20}; | |
TreeNode tree = {&l1, &r1, 10}; | |
// Grab the answer | |
int previousValue = INT_MIN; | |
int answer = isTreeSorted(&tree, &previousValue) == 1; | |
// Print the result | |
printf("sorted = %s, correct = %s\n", boolToString(answer), boolToString(answer == desiredAnswer)); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment