fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class node{
  5. public:
  6.     int data;
  7.     node*left;
  8.     node*right;
  9.  
  10.     node(int d){
  11.         data = d;
  12.         left = NULL;
  13.         right = NULL;
  14.     }
  15. };
  16.  
  17.  
  18. ///Print the tree level by level
  19. void levelOrderPrint2(node*root){
  20.  
  21.     queue<node*> q;
  22.     q.push(root);
  23.     q.push(NULL);
  24.  
  25.     while(!q.empty()){
  26.         node* f = q.front();
  27.         if(f==NULL){
  28.             q.pop();
  29.             cout<<endl;
  30.             if(!q.empty()){
  31.                 q.push(NULL);
  32.             }
  33.         }
  34.         else{
  35.             q.pop();
  36.             cout<<f->data<<" ";
  37.  
  38.             if(f->left){
  39.                 q.push(f->left);
  40.             }
  41.             if(f->right){
  42.                 q.push(f->right);
  43.             }
  44.         }
  45.     }
  46. }
  47.  
  48. void printPreorder(node*root){
  49.     if(root==NULL){
  50.         return;
  51.     }
  52.     cout<<root->data<<" ";
  53.     printPreorder(root->left);
  54.     printPreorder(root->right);
  55. }
  56.  
  57. void printInorder(node*root){
  58.     if(root==NULL){
  59.         return;
  60.     }
  61.     printInorder(root->left);
  62.     cout<<root->data<<" ";
  63.     printInorder(root->right);
  64. }
  65.  
  66. void postOrder(node*root){
  67.     if(root==NULL){
  68.         return;
  69.     }
  70.     postOrder(root->left);
  71.     postOrder(root->right);
  72.     cout<<root->data<<" ";
  73.  
  74. }
  75. /// Builds a BST
  76. node* insertInBST(node*root,int data){
  77.     if(root==NULL){
  78.         root = new node(data);
  79.         return root;
  80.     }
  81.     ///Rec Case
  82.     if(data <= root->data){
  83.         root->left = insertInBST(root->left,data);
  84.     }
  85.     else{
  86.         root->right = insertInBST(root->right,data);
  87.     }
  88.     return root;
  89. }
  90.  
  91. void takeInput(node*&root){
  92.  
  93.     int data;
  94.     cin>>data;
  95.  
  96.     while(data!=-1){
  97.         root = insertInBST(root,data);
  98.         cin>>data;
  99.     }
  100. }
  101. ostream& operator<<(ostream&os, node*root){
  102.     levelOrderPrint2(root);
  103.     return os;
  104. }
  105. istream& operator>>(istream&is, node*&root){
  106.     takeInput(root);
  107.     return is;
  108. }
  109. ///Time Complexity of the search function
  110. bool search(node*root,int data){
  111.     if(root==NULL){
  112.         return false;
  113.     }
  114.     if(root->data==data){
  115.         return true;
  116.     }
  117.     if(root->data < data){
  118.         return search(root->right,data);
  119.     }
  120.     return search(root->left,data);
  121. }
  122. /// Pair
  123. class myPair{
  124. public:
  125.     int height;
  126.     bool balance;
  127. };
  128.  
  129. myPair isBalanced(node*root){
  130.     myPair p;
  131.     if(root==NULL){
  132.         p.height = 0;
  133.         p.balance = true;
  134.         return p;
  135.     }
  136.  
  137.     myPair leftTree = isBalanced(root->left);
  138.     myPair rightTree = isBalanced(root->right);
  139.  
  140.     int diff = abs(leftTree.height - rightTree.height);
  141.  
  142.     if(diff<=1 && leftTree.balance && rightTree.balance){
  143.             p.balance = true;
  144.     }
  145.     else{
  146.         p.balance = false;
  147.     }
  148.     p.height = max(leftTree.height,rightTree.height) + 1;
  149.     return p;
  150. }
  151.  
  152. /// Count BST - HW - Catalan Number
  153. int countBSTs(int n){
  154.  
  155.  
  156. }
  157. ///Min Node
  158. node* minNode(node*root){
  159.     while(root->left!=NULL){
  160.         root = root->left;
  161.     }
  162.     return root;
  163. }
  164.  
  165.  
  166. /// Delete in BST
  167. node* deleteNode(node *root,int key){
  168.     if(root==NULL){
  169.         return NULL;
  170.     }
  171.     if(root->data == key){
  172.         ///Three cases 0 child, 1 child, 2 children
  173.         if(root->left==NULL && root->right==NULL){
  174.            // cout<<"Here "<<endl;
  175.             delete root;
  176.             return NULL;
  177.         }
  178.         /// Single Child
  179.         if(root->left==NULL && root->right!=NULL){
  180.                 node*temp = root->right;
  181.                 delete root;
  182.                 return temp;
  183.         }
  184.         if(root->left!=NULL && root->right==NULL){
  185.                 node* temp = root->left;
  186.                 delete root;
  187.                 return temp;
  188.         }
  189.         /// 2 children
  190.         /// find min node in right subtree
  191.             node* replaceMent = minNode(root->right);
  192.             root->data = replaceMent->data;
  193.             root->right =  deleteNode(root->right,replaceMent->data);
  194.             return root;
  195.     }
  196.     else if(root->data > key){
  197.         root->left = deleteNode(root->left,key);
  198.         return root;
  199.     }
  200.     else{
  201.         root->right = deleteNode(root->right,key);
  202.         return root;
  203.     }
  204. }
  205.  
  206.  
  207. node* arrayToBST(int *a,int s,int e){
  208.     if(s>e){
  209.         return NULL;
  210.     }
  211.     int mid = (s+e)/2;
  212.     node* root = new node(a[mid]);
  213.     root->left = arrayToBST(a,s,mid-1);
  214.     root->right = arrayToBST(a,mid+1,e);
  215.     return root;
  216. }
  217.  
  218. bool isBST(node*root,int minV=INT_MIN, int maxV = INT_MAX){
  219.     if(root==NULL){
  220.         return true;
  221.     }
  222.     if(root->data >= minV && root->data <maxV
  223.        && isBST(root->left,minV,root->data) &&
  224.        isBST(root->right,root->data,maxV)){
  225.         return true;
  226.     }
  227.     return false;
  228. }
  229.  
  230. class LinkedList{
  231. public:
  232.     node*head;
  233.     node*tail;
  234. };
  235.  
  236. LinkedList tree2LL(node*root){
  237.     LinkedList l;
  238.     if(root==NULL){
  239.         l.head = l.tail = NULL;
  240.         return l;
  241.     }
  242.     else if(root->left==NULL && root->right==NULL){
  243.         l.head = root;
  244.         l.tail = root;
  245.     }
  246.     else if(root->left!=NULL && root->right==NULL){
  247.         LinkedList leftLL = tree2LL(root->left);
  248.         leftLL.tail->right = root;
  249.  
  250.         l.head = leftLL.head;
  251.         l.tail = root;
  252.     }
  253.     else if(root->left==NULL && root->right!=NULL){
  254.         LinkedList rightLL = tree2LL(root->right);
  255.         root->right = rightLL.head;
  256.         l.head = root;
  257.         l.tail = rightLL.tail;
  258.     }
  259.     else{
  260.         LinkedList leftLL = tree2LL(root->left);
  261.         LinkedList rightLL = tree2LL(root->right);
  262.  
  263.         leftLL.tail->right = root;
  264.         root->right = rightLL.head;
  265.  
  266.         l.head = leftLL.head;
  267.         l.tail = rightLL.tail;
  268.     }
  269.     return l;
  270.  
  271. }
  272.  
  273.  
  274.  
  275. int main(){
  276.  
  277.     node*root = NULL;
  278.     int a[] = {1,2,4,5,6,8,9,10};
  279.     int n = sizeof(a)/sizeof(int);
  280.  
  281.     root = arrayToBST(a,0,n-1);
  282.     if(isBST(root)){
  283.         cout<<"Yes its bst"<<endl;
  284.     }
  285.     else{
  286.         cout<<"not a bst"<<endl;
  287.     }
  288.     cout<<root<<endl;
  289.  
  290.     LinkedList l = tree2LL(root);
  291.     node*temp = l.head;
  292.  
  293.     while(temp!=NULL){
  294.         cout<<temp->data<<"->";
  295.         temp = temp->right;
  296.     }
  297.     cout<<"NULL"<<endl;
  298. return 0;
  299. }
  300.  
  301.  
  302.  
Success #stdin #stdout 0s 16072KB
comments (?)
stdin 
Standard input is empty
stdout 
Yes its bst
5 
2 8 
1 4 6 9 
10 

1->2->4->5->6->8->9->10->NULL
https://ideone.com/NFy0FN
language:
C++14 (gcc 8.3)
created:
6 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!