fork(8) download 
  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. struct node {
  5. 	int data;
  6. 	struct node * left;
  7. 	struct node * right;
  8. } * root = NULL;
  9.  
  10. struct node * insertNode(struct node * tNode, int value) {
  11. 	if(tNode == NULL) {
  12. 		struct node * newNode = (struct node *)malloc(sizeof(struct node));
  13. 		newNode->data = value;
  14. 		newNode->left = NULL;
  15. 		newNode->right = NULL;
  16. 		return newNode;
  17. 	}
  18. 	if(tNode->data > value)
  19. 		tNode->left = insertNode(tNode->left, value);
  20. 	else
  21. 		tNode->right = insertNode(tNode->right, value);
  22. 	return tNode;
  23. }
  24.  
  25. void buildTree(int a[], int N) {
  26. 	for(int i = 0; i < N; i++) {
  27. 		if(i) {
  28. 			insertNode(root, a[i]);
  29. 		} else {
  30. 			root = insertNode(NULL, a[i]);
  31. 		}
  32. 	}
  33. }
  34.  
  35. int secondSmallestInBST(struct node * tNode) {
  36.     if( tNode==NULL || (tNode->left==NULL && tNode->right==NULL) )  // case 1 and 2
  37.         exit;
  38.     if(tNode->left == NULL){                     // case 3
  39.         tNode=tNode->right;
  40.         while(tNode->left!=NULL){
  41.             tNode=tNode->left;
  42.         }
  43.         return tNode->data;
  44.     }                                                     // general case.
  45.     node * parent=tNode,* child = tNode->left;
  46.     while(child->left!=NULL){
  47.     	parent = child;
  48.     	child = child->left;
  49.     }
  50.     return parent->data;
  51. }
  52.  
  53.  
  54.  
  55. int main() {
  56. 	int N;
  57. 	cin >> N;
  58. 	int arr[N];
  59. 	for(int i = 0; i < N; i++) {
  60. 		cin >> arr[i];
  61. 	}
  62. 	buildTree(arr, N);
  63. 	cout << secondSmallestInBST(root) << endl;
  64. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin 
3 50 30 80
stdout 
50
https://ideone.com/m6zu8D
2nd smallest in bst
language:
C++14 (gcc 8.3)
created:
9 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!