fork download
copy 
  1. /* 
  2.  * File:   isBSTIterative.c
  3.  * Author: srkrishnan
  4.  *
  5.  * Created on June 30, 2011, 2:18 PM
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10.  
  11. typedef struct Tnode {
  12.     int data;
  13.     struct Tnode *left;
  14.     struct Tnode *right;
  15. } Tnode;
  16.  
  17. typedef struct List {
  18.     Tnode *data;
  19.     struct List *link;
  20. } List;
  21.  
  22. List *head = NULL;
  23.  
  24. List* createlistnode() {
  25.     List *n = (List*) malloc(sizeof (List));
  26.     n->data = NULL;
  27.     n->link = NULL;
  28.     return n;
  29. }
  30.  
  31. Tnode* createnode(int data) {
  32.     Tnode *n = (Tnode*) malloc(sizeof (Tnode));
  33.     n->left = n->right = NULL;
  34.     n->data = data;
  35.     return n;
  36. }
  37.  
  38. void push(Tnode *root) {
  39.     List *tmp = NULL;
  40.     if (head == NULL) {
  41.         head = createlistnode();
  42.         head->data = root;
  43.         return;
  44.     }
  45.     tmp = createlistnode();
  46.     tmp->data = root;
  47.     tmp->link = head;
  48.     head = tmp;
  49. }
  50.  
  51. Tnode* pop() {
  52.     List *tmp = NULL;
  53.     Tnode *t=NULL;
  54.     if (head != NULL) {
  55.         tmp = head;
  56.         head = head->link;
  57.         t=tmp->data;
  58.     }
  59.     return t;
  60. }
  61.  
  62. int isBSTiterative(Tnode *root) {
  63.     int prev = -99999;
  64.     Tnode *node = NULL;
  65.     while (root) {
  66.         push(root);
  67.         if (root->left == NULL) {
  68.  
  69.             do {
  70.                 node = pop();
  71.                 if (node->data < prev)
  72.                     return 0;
  73.                 prev = node->data;
  74.                 root = node->right;
  75.             } while (root == NULL && isempty() != 1);
  76.         } else {
  77.             root = root->left;
  78.         }
  79.     }
  80.     return 1;
  81. }
  82.  
  83. int isempty() {
  84.     if (head == NULL)
  85.         return 1;
  86.     return 0;
  87. }
  88.  
  89. int main(int argc, char** argv) {
  90.  
  91.     Tnode *root;
  92.  
  93.     root = createnode(15);
  94.  
  95.     root->left = createnode(7);
  96.     root->right = createnode(25);
  97.  
  98.     root->left->left = createnode(3);
  99.     root->left->right = createnode(10);
  100.  
  101.     root->right->left = NULL;
  102.     root->right->right = createnode(50);
  103.  
  104.     root->left->right->left = createnode(8);
  105.     root->left->right->right = createnode(12);
  106.  
  107.     root->left->right->left->left = NULL;
  108.     root->left->right->left->right = createnode(9);
  109.  
  110.     root->left->right->right->left = createnode(11);
  111.     root->left->right->right->right = createnode(14);
  112.  
  113.     root->right->right->left = createnode(30);
  114.     root->right->right->right = createnode(55);
  115.  
  116.     root->right->right->right->left = createnode(52);
  117.     root->right->right->right->right = NULL;
  118.  
  119.     printf("%d", isBSTiterative(root));
  120.  
  121.     return (EXIT_SUCCESS);
  122. }
  123.  
stdin
copy 
Standard input is empty
compilation info 
prog.c: In function ‘isBSTiterative’:
prog.c:75: warning: implicit declaration of function ‘isempty’
stdout
copy 
1
https://ideone.com/VjjqN
language:
C (gcc 8.3)
created:
14 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!