Table of contents

Question:

Solution:

2.1.

Approach1:

2.2.

Better Approach

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Check for Binary Search Tree

Q: Q1: What is a Binary Search Tree in data structure?Ans1:The Binary Search Tree data structure is a node-based binary tree with the following properties:

The left subtree contains only nodes whose key value is smaller than the root's key value.The right subtree contains only nodes whose key value is greater than the root's key value.Each left and right subtree must be a Binary Search Tree.

Q: Q2: What is a Binary Tree used for?Ans2: Binary Trees are mainly used for searching and sorting since they allow hierarchical data storage. Some common operations on a Binary Tree include Insertion, deletion, and traversal.

Q3: Where can I practice Binary Search Tree Questions?Ans3: Read and Practice important interview-related Binary Search Tree questions here. It is free and covers basic to advanced coding questions on Binary Search Tree.

Author GAZAL ARORA

Do you think IIT Guwahati certified course can help you in your career?

Yes

Question:

Given an array, A of size N. Find whether it is possible to make a Binary Search Tree with elements of A such that the greatest common divisor of any two vertices connected by a common edge is > 1. Print Yes if possible, otherwise print No.

Read more about Binary Search Trees from here.

Examples:

Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Input: A = { 3, 18, 6, 9, 36, 108 }

Output: Yes

Explanation: One of the possible BTS is given below. Here vertices of every edge have GCD > 1.

Input: A = {2, 47}
Output: No

Explanation: GCD of 2 and 47 is 1.

Recommended: Please try to solve it yourself before moving on to the solution.

Solution:

Approach1:

The idea is to use Dynamic Programming (DP).

Let DP(l, r, root) be a DP array with values 0 or 1 determining if it is possible to create a BST root at the root from the sub-segment [ l, r ] of the given array.

Calculating DP(l, r, root) requires extracting the (leftRoot) root of the left subtree from [l..root – 1] and (rightRoot) root of the right subtree from [root + 1..right] in the following manner:

gcd(a_root, a_rightRoot) > 1
gcd(a_root, a_leftRoot) > 1
DP(l, root-1, leftRoot) = 1
DP(root+1, r, rightRoot) = 1

In DP(l, r, root), l can take n values, r can take n values, and root can also take n values. Therefore there are n³ DP states.

Also, the transition time for DP will be O(n). Hence, a total of n⁴ time complexity of this solution.

Better Approach

Let’s define DP differently; let DP_New(l, r, state) be a DP, where a state can be 0 or 1.

Here we can calculate DP(l, r, root) from DP_New(l, root - 1, 1) and DP_New(root + 1, r, 0).

Here l can take n values, r can take n values, and state can take two values. Therefore there are n² DP states.

Also, the transition time for DP will be O(n). Hence, it has a total of n³ time complexity which is enough to pass.

C++

#include <bits/stdc++.h>
using namespace std;

// Return 1 it is possible to make BST from l to r with given state
int isPossibleWithStates(int l, int r, int state, int a[], vector<vector<vector<int>>> &dp){
// Base condition.
if (l > r)
return 1;

if (dp[l][r][state] != -1)
return dp[l][r][state];

// Deciding root by state value
int root;
if (state == 1)
root = a[r + 1];
else
root = a[l - 1];

for (int i = l; i <= r; i++) {

// checking the gcd condition.
if (__gcd(a[i], root) > 1) {

int x = isPossibleWithStates(l, i - 1, 1, a, dp);
if (x != 1)
continue;
int y = isPossibleWithStates(i + 1, r, 0, a, dp);

if (x == 1 && y == 1){
return dp[l][r][state] = 1;
}
}
}

// If not possible.
return dp[l][r][state] = 0;
}

bool isPossible(int a[], int n, vector<vector<vector<int>>> &dp){
// Sort the given array.
sort(a, a + n);

// Check it is possible to create BST rooted at i.

for (int i = 0; i < n; i++){
// Check at both sides.
if (isPossibleWithStates(0, i - 1, 1, a, dp) && isPossibleWithStates(i + 1, n - 1, 0, a, dp))
return true;
}
return false;
}

int main(){

int a[] = { 3, 18, 6, 9, 36, 108 };
int n = sizeof(a) / sizeof(a[0]);
vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(2, -1)));
if (isPossible(a, n, dp))
cout << "Yes";
else
cout << "No";
return 0;
}

Output:

Time Complexity: O(N³)

Frequently Asked Questions

Q1: What is a Binary Search Tree in data structure?
Ans1:The Binary Search Tree data structure is a node-based binary tree with the following properties:

The left subtree contains only nodes whose key value is smaller than the root's key value.
The right subtree contains only nodes whose key value is greater than the root's key value.
Each left and right subtree must be a Binary Search Tree.

Q2: What is a Binary Tree used for?
Ans2: Binary Trees are mainly used for searching and sorting since they allow hierarchical data storage. Some common operations on a Binary Tree include Insertion, deletion, and traversal.

Q3: Where can I practice Binary Search Tree Questions?
Ans3: Read and Practice important interview-related Binary Search Tree questions here. It is free and covers basic to advanced coding questions on Binary Search Tree.

Key Takeaways

This article solved a DP-based problem where an array was given and a condition to satisfy; we needed to find if a Binary Search Tree can be created from the given array or not. We solved the problem with a DP approach taking o(n³) time complexity.

Check out this problem - Diameter Of Binary Tree

You can practice more DP questions from here.

If you are new to DP and want to do a course covering all the DP concepts from basics to advanced level. Enroll Now!

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.