jain12

Construct BST from preorder traversal

Mar 11th, 2020
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.91 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. class Node{
  4.   public:
  5.       int data;
  6.       Node *left,*right;
  7.       Node(int key){
  8.         data=key;
  9.         left=right=NULL;
  10.         }
  11.   };
  12.  
  13. void Inorder(Node *root){
  14.    if(root==NULL)
  15.      return;
  16.    Inorder(root->left);
  17.    cout<<" "<<root->data;
  18.    Inorder(root->right);
  19.    }
  20.  
  21. void Insert(Node **root_ref,int key){
  22.   if(*root_ref==NULL){
  23.     *root_ref=new Node(key);
  24.     return;
  25.     }
  26.   if((*root_ref)->data<key)
  27.     Insert(&((*root_ref)->right),key);
  28.   else
  29.      if((*root_ref)->data>key)
  30.        Insert(&((*root_ref)->left),key);
  31.   }
  32.  
  33. int main(){
  34.  cout<<"no. of nodes in tree";
  35.  int n;
  36.  cin>>n;
  37.  int arr[n];
  38.  cout<<endl<<"enter values in preorder :";
  39.  for(int i=0;i<n;i++)
  40.     cin>>arr[i];
  41.  Node *root=NULL;
  42.  for(int i=0;i<n;i++)
  43.    Insert(&root,arr[i]);
  44.  cout<<endl<<"Inorder of constructed BST tree is :";
  45.  Inorder(root);
  46.  return 0;
  47.  }
Add Comment
Please, Sign In to add comment