Inorder Traversal and BST
PROBLEM :
Given an array, write a program that prints 1 if array represents Inorder traversal of a BST, else prints 0. Note that all keys in BST must be unique.
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N, N is the size of array.
The second line of each test case contains N input C[i].
Output:
Print 1 array represents BST, else 0.
Constraints:
1 = T = 100
1 = N = 500
1 = Keys in BST = 1200
Example:
Input
3
5
10 20 30 40 50
6
90 80 100 70 40 30
3
1 1 2
Output
1
0
0
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int main()
{
int t,no,a[500],i,flag ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>a[i] ;
flag=1 ;
for(i=0;i<no-1;i++)
{
if(a[i]>=a[i+1])
flag=0 ;
}
if(flag==0)
cout<<0 ;
else
cout<<1 ;
cout<<endl ;
}
return 0;
}
---------------------------------------------------------------------------------
Given an array, write a program that prints 1 if array represents Inorder traversal of a BST, else prints 0. Note that all keys in BST must be unique.
Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N, N is the size of array.
The second line of each test case contains N input C[i].
Output:
Print 1 array represents BST, else 0.
Constraints:
1 = T = 100
1 = N = 500
1 = Keys in BST = 1200
Example:
Input
3
5
10 20 30 40 50
6
90 80 100 70 40 30
3
1 1 2
Output
1
0
0
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
int main()
{
int t,no,a[500],i,flag ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>a[i] ;
flag=1 ;
for(i=0;i<no-1;i++)
{
if(a[i]>=a[i+1])
flag=0 ;
}
if(flag==0)
cout<<0 ;
else
cout<<1 ;
cout<<endl ;
}
return 0;
}
---------------------------------------------------------------------------------
Comments
Post a Comment