fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])
  5.  
  6. /* just add elements to test */
  7. /* NOTE: A sorted array results in skewed tree */
  8. int ele[] = { 20, 8, 22, 4, 12, 10, 14 };
  9.  
  10. /* same alias */
  11. typedef struct node_t node_t;
  12.  
  13. /* Binary tree node */
  14. struct node_t
  15. {
  16.     int data;
  17.  
  18.     node_t* left;
  19.     node_t* right;
  20. };
  21.  
  22. /* simple stack that stores node addresses */
  23. typedef struct stack_t stack_t;
  24.  
  25. /* initial element always NULL, uses as sentinal */
  26. struct stack_t
  27. {
  28.     node_t*  base[ARRAY_SIZE(ele) + 1];
  29.     int      stackIndex;
  30. };
  31.  
  32. /* pop operation of stack */
  33. node_t *pop(stack_t *st)
  34. {
  35.     node_t *ret = NULL;
  36.  
  37.     if( st && st->stackIndex > 0 )
  38.     {
  39.         ret = st->base[st->stackIndex];
  40.         st->stackIndex--;
  41.     }
  42.  
  43.     return ret;
  44. }
  45.  
  46. /* push operation of stack */
  47. void push(stack_t *st, node_t *node)
  48. {
  49.     if( st )
  50.     {
  51.         st->stackIndex++;
  52.         st->base[st->stackIndex] = node;
  53.     }
  54. }
  55.  
  56. /* Iterative insertion
  57.    Recursion is least preferred unless we gain something
  58. */
  59. node_t *insert_node(node_t *root, node_t* node)
  60. {
  61.     /* A crawling pointer */
  62.     node_t *pTraverse = root;
  63.     node_t *currentParent = root;
  64.  
  65.     // Traverse till appropriate node
  66.     while(pTraverse)
  67.     {
  68.         currentParent = pTraverse;
  69.  
  70.         if( node->data < pTraverse->data )
  71.         {
  72.             /* left subtree */
  73.             pTraverse = pTraverse->left;
  74.         }
  75.         else
  76.         {
  77.             /* right subtree */
  78.             pTraverse = pTraverse->right;
  79.         }
  80.     }
  81.  
  82.     /* If the tree is empty, make it as root node */
  83.     if( !root )
  84.     {
  85.         root = node;
  86.     }
  87.     else if( node->data < currentParent->data )
  88.     {
  89.         /* Insert on left side */
  90.         currentParent->left = node;
  91.     }
  92.     else
  93.     {
  94.         /* Insert on right side */
  95.         currentParent->right = node;
  96.     }
  97.  
  98.     return root;
  99. }
  100.  
  101. /* Elements are in an array. The function builds binary tree */
  102. node_t* binary_search_tree(node_t *root, int keys[], int const size)
  103. {
  104.     int iterator;
  105.     node_t *new_node = NULL;
  106.  
  107.     for(iterator = 0; iterator < size; iterator++)
  108.     {
  109.         new_node = (node_t *)malloc( sizeof(node_t) );
  110.  
  111.         /* initialize */
  112.         new_node->data   = keys[iterator];
  113.         new_node->left   = NULL;
  114.         new_node->right  = NULL;
  115.  
  116.         /* insert into BST */
  117.         root = insert_node(root, new_node);
  118.     }
  119.  
  120.     return root;
  121. }
  122.  
  123. node_t *k_smallest_element_inorder(stack_t *stack, node_t *root, int k)
  124. {
  125.     stack_t *st = stack;
  126.     node_t *pCrawl = root;
  127.  
  128.     /* move to left extremen (minimum) */
  129.     while( pCrawl )
  130.     {
  131.         push(st, pCrawl);
  132.         pCrawl = pCrawl->left;
  133.     }
  134.  
  135.     /* pop off stack and process each node */
  136.     while( pCrawl = pop(st) )
  137.     {
  138.         /* each pop operation emits one element
  139.            in the order
  140.         */
  141.         if( !--k )
  142.         {
  143.             /* loop testing */
  144.            // st->stackIndex = 0;
  145.             break;
  146.         }
  147.  
  148.         /* there is right subtree */
  149.         if( pCrawl->right )
  150.         {
  151.             /* push the left subtree of right subtree */
  152.             pCrawl = pCrawl->right;
  153.             while( pCrawl )
  154.             {
  155.                 push(st, pCrawl);
  156.                 pCrawl = pCrawl->left;
  157.             }
  158.  
  159.             /* pop off stack and repeat */
  160.         }
  161.     }
  162.  
  163.     /* node having k-th element or NULL node */
  164.     return pCrawl;
  165. }
  166.  
  167. /* Driver program to test above functions */
  168. int main(void)
  169. {
  170.     node_t* root = NULL;
  171.     stack_t stack = { {0}, 0 };
  172.     node_t *kNode = NULL;
  173.  
  174.     int k = 5;
  175.  
  176.     /* Creating the tree given in the above diagram */
  177.     root = binary_search_tree(root, ele, ARRAY_SIZE(ele));
  178.  
  179.     kNode = k_smallest_element_inorder(&stack, root, k);
  180.  
  181.     if( kNode )
  182.     {
  183.         printf("kth smallest elment for k = %d is %d", k, kNode->data);
  184.     }
  185.     else
  186.     {
  187.         printf("There is no such element");
  188.     }
  189.  
  190.     getchar();
  191.     return 0;
  192. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
kth smallest elment for k = 5 is 14
https://ideone.com/8h5Bc3
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!