Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Binary Search Tree Problem

Given a binary tree, check if it is a binary search tree (BST). A valid BST does not have to be complete or balanced.

Consider the below definition of a BST:

1. All nodes values of left subtree are less than or equal to parent node value
2. All nodes values of right subtree are greater than or equal to parent node value
3. Both left subtree and right subtree must be a BST
4. By definition, NULL tree is a BST
5. By definition, trees having a single node or leaf nodes are BST.

Example One

Input:

Output: false

Left child value 200 is greater than the parent node value 100; violates the definition of BST.

Example Two

Input:

Output: true

Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: Return true if the input tree is a BST or false otherwise

Constraints:

• 0 <= number of nodes <= 100000
• -10^9 <= values stored in the nodes <= 10^9
• Return value must be boolean

### Solutions

We provided two solutions, both are optimal in terms of time and space complexity, though algorithms are different.

### 1) other_solution.cpp:

In the following three examples, tree A and B is a BST, where tree C is not:

In other_solution.cpp we use the definition of BST quite literally. For every node, recursively, we check that all values in the left subtree are <= current node value and all values in the right subtree are >= current node value. We also propagate all the "<=" and ">=" conditions down the recursion tree (they get more specific, more narrow as we go down the tree), effectively forming a valid range for every node we check. For example, in the following tree,

the requirements for X are both X>=1 and X<=4. Further, valid range for Y is Y>=X and Y<=4. Notice that because X>=1 holds true (X is checked before Y, higher up in the recursion tree), the effective valid range for Y is narrower than one for X; that way the range gets narrower as we go deeper down the tree. For better understanding please look at the solution.

Time Complexity:

O(n) where n denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the node value lies within a range or not, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate  n + (n-1) → 2n-1 times can be represented as O(n) complexity.

Auxiliary Space:

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

Space complexity:

O(n).

``````
// -------- START --------

bool isBSTHelper(TreeNode *root, int min, int max){
// NULL node check
if(root == NULL){
return true;
}
// current node value is not within valid range
if(root->val>max || root->valleft_ptr, min, root->val) && isBSTHelper(root->right_ptr, root->val, max);
}

bool isBST(TreeNode* root){
// empty or null tree check
if(root==NULL){
return true;
}
int min = INT_MIN;
int max = INT_MAX;
return isBSTHelper(root, min, max);
}

// -------- END --------
``````

### 2) optimal_solution.cpp:

In optimal_solution.cpp solution we have used in-order traversal property of a BST to validate whether it is a BST or not. If we store the values in an array during in-order traversal, it will be a sorted array if the given tree is BST. To check if an array is sorted or not, we just need to compare an element with the previous element of the array. We can do this while traversing the tree instead of storing the values in an array which will reduce space complexity. To achieve this, we have used a variable which stores the last visited nodes value at any time. So, when we are in a node, we can compare if the current node value is greater or equal to the previous node value. If this condition fails for any node then the given tree is not a BST. Otherwise it is.

Time Complexity:

O(n) where n denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the current node value is greater or equal to the previous node value, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate  n + (n-1) → 2n-1 times can be represented as O(n) complexity.

Auxiliary Space:

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

Space Complexity:

O(n).

``````
// -------- START --------

bool isBSTHelper(TreeNode *root, int &prev){
// NULL node check
if(root == NULL){
return true;
}

// check if left subtree is bst or not
bool isLeftSubtreeBST = isBSTHelper(root->left_ptr, prev);

// Check if current node value is greater or equal to the max value of left subtree nodes
if(root->val < prev){
return false;
}

// update the prev variable by current node value as each value of right subtree must be greater or equal
// to the current root value
prev = root->val;
// true when both left and right subtrees are valid BST
bool isRightSubtreeBST = isBSTHelper(root->right_ptr, prev);

// Bitwise AND operation to return true only when both subtree is BST, otherwise false
return (isLeftSubtreeBST && isRightSubtreeBST);
}

bool isBST(TreeNode* root){
// empty or null tree check
if(root==NULL){
return true;
}
int min = INT_MIN;
return isBSTHelper(root, min);
}

// -------- END --------
``````

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Binary Search Tree Problem

Given a binary tree, check if it is a binary search tree (BST). A valid BST does not have to be complete or balanced.

Consider the below definition of a BST:

1. All nodes values of left subtree are less than or equal to parent node value
2. All nodes values of right subtree are greater than or equal to parent node value
3. Both left subtree and right subtree must be a BST
4. By definition, NULL tree is a BST
5. By definition, trees having a single node or leaf nodes are BST.

Example One

Input:

Output: false

Left child value 200 is greater than the parent node value 100; violates the definition of BST.

Example Two

Input:

Output: true

Notes

Input Parameters: There is only one argument named root denoting the root of the input tree.

Output: Return true if the input tree is a BST or false otherwise

Constraints:

• 0 <= number of nodes <= 100000
• -10^9 <= values stored in the nodes <= 10^9
• Return value must be boolean

### Solutions

We provided two solutions, both are optimal in terms of time and space complexity, though algorithms are different.

### 1) other_solution.cpp:

In the following three examples, tree A and B is a BST, where tree C is not:

In other_solution.cpp we use the definition of BST quite literally. For every node, recursively, we check that all values in the left subtree are <= current node value and all values in the right subtree are >= current node value. We also propagate all the "<=" and ">=" conditions down the recursion tree (they get more specific, more narrow as we go down the tree), effectively forming a valid range for every node we check. For example, in the following tree,

the requirements for X are both X>=1 and X<=4. Further, valid range for Y is Y>=X and Y<=4. Notice that because X>=1 holds true (X is checked before Y, higher up in the recursion tree), the effective valid range for Y is narrower than one for X; that way the range gets narrower as we go deeper down the tree. For better understanding please look at the solution.

Time Complexity:

O(n) where n denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the node value lies within a range or not, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate  n + (n-1) → 2n-1 times can be represented as O(n) complexity.

Auxiliary Space:

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

Space complexity:

O(n).

``````
// -------- START --------

bool isBSTHelper(TreeNode *root, int min, int max){
// NULL node check
if(root == NULL){
return true;
}
// current node value is not within valid range
if(root->val>max || root->valleft_ptr, min, root->val) && isBSTHelper(root->right_ptr, root->val, max);
}

bool isBST(TreeNode* root){
// empty or null tree check
if(root==NULL){
return true;
}
int min = INT_MIN;
int max = INT_MAX;
return isBSTHelper(root, min, max);
}

// -------- END --------
``````

### 2) optimal_solution.cpp:

In optimal_solution.cpp solution we have used in-order traversal property of a BST to validate whether it is a BST or not. If we store the values in an array during in-order traversal, it will be a sorted array if the given tree is BST. To check if an array is sorted or not, we just need to compare an element with the previous element of the array. We can do this while traversing the tree instead of storing the values in an array which will reduce space complexity. To achieve this, we have used a variable which stores the last visited nodes value at any time. So, when we are in a node, we can compare if the current node value is greater or equal to the previous node value. If this condition fails for any node then the given tree is not a BST. Otherwise it is.

Time Complexity:

O(n) where n denotes the number of nodes.

As we are traversing all the nodes of the tree to check if the current node value is greater or equal to the previous node value, hence we have to iterate through all the nodes and edges of the tree. A tree with n nodes have (n-1) edges. So, we have to iterate  n + (n-1) → 2n-1 times can be represented as O(n) complexity.

Auxiliary Space:

O(n) where n denotes the number of nodes.

As we are calling functions in recursion, so in the worst case functional stack can have n number of function calls which is equal to the number of nodes of the given tree. Hence auxiliary space for that is O(n)

Space Complexity:

O(n).

``````
// -------- START --------

bool isBSTHelper(TreeNode *root, int &prev){
// NULL node check
if(root == NULL){
return true;
}

// check if left subtree is bst or not
bool isLeftSubtreeBST = isBSTHelper(root->left_ptr, prev);

// Check if current node value is greater or equal to the max value of left subtree nodes
if(root->val < prev){
return false;
}

// update the prev variable by current node value as each value of right subtree must be greater or equal
// to the current root value
prev = root->val;
// true when both left and right subtrees are valid BST
bool isRightSubtreeBST = isBSTHelper(root->right_ptr, prev);

// Bitwise AND operation to return true only when both subtree is BST, otherwise false
return (isLeftSubtreeBST && isRightSubtreeBST);
}

bool isBST(TreeNode* root){
// empty or null tree check
if(root==NULL){
return true;
}
int min = INT_MIN;
return isBSTHelper(root, min);
}

// -------- END --------
``````

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*