ECAUG204 - Editorial

editorial
,
1

PROBLEM LINK:

Encoding August’20
Problem

Author: shrivas7
Tester: sandeep1103
Editorialist: shrivas7

DIFFICULTY:

Easy

PREREQUISITES:

Maps,Set,Hashing

EXPLANATION:

We know that in a Binary Search Tree the value of the left child of a node is less than that of the node, the value of the right child is greater than that of the node and there must not be any duplicate elements. So we need to check whether any such node values exist in the array or not. In other words we need to make sure that all the elements of the array are distinct for the construction of BST.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t,n,x;
    cin>>t;
    while(t--)
    {
        cin>>n;
        map<int,int> mp;
        int fl=1;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            mp[x]++;
            if(mp[x]>1)
            	fl=0;
        }
       
        if(fl)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
}
Tester's Solution 
 #include <bits/stdc++.h>
#define ll long long 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;
 
 
void solve(){
 
	int i, j, n;
	cin >> n;
	set <int> st;
 
	for(i = 0; i < n; ++i){
		cin >> j;
		st.insert(j);
	}
 
	cout << (((st.size() == n))?"Yes":"No");
	ln; 
 
}
int main(){
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
 
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
	#endif
 
	int t = 1;
	cin >> t;
	while(t--)
		solve();
}
2 Likes
2

But,it was not written anywhere in the problem that duplicates are not allowed.
Infact ,even if we have duplicates still we can create a binary search tree.
For ex-> If we have
A[]={7,7,7,1,2,3,4}
Binary Search tree-:

      4
    /  \
   3    7
  /  \
  2  7
 / \
1   7
3

This BST is not valid , because the maximum value in the left subtree of the each node should be less than current node value.
This one is valid.

            4
         /   \
        3     7
      /      /
     2      7
   /       /
  1       7

But yes in the problem they didn’t mention anything about duplicates :sweat_smile: .At first even i considered answer would be Yes for every input :joy: