Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
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
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

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
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

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

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

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.

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

Recommended Posts

All Posts