Is given Tree a BST or not?

You are given a binary tree, you need to determine if the tree is a valid BST or not? For a tree to be a BST, the left child of a node should have a value less than the node’s value and the right child of the node should have a value greater than the node’s value and the property should hold true for all the subtrees.

The above tree satisfies all the properties of a Binary Search Tree.

Algorithm

Instead of guessing the answer solely based on the node’s value and it’s children, we need to pass on the information from the parent nodes as well.

For example, in the above tree, the node 20 has value greater than it’s left child and less than it’s right child. If based on this condition only, we determine the validity of the tree, than the answer would be true. However, we can see that the node 5 which is on the right subtree of the root node has a value less than the root node 20. Thus, the actual answer should be False. Thus, we need to pass on the parent node’s information downwards.

At each node, we need to check the following conditions –

  1. If the current node is the left child of the parent, then it must be smaller than the it’s parent and it also has to pass on the value from it’s parent to it’s right subtree so as to make sure that none of the nodes in that particular subtree has a value greater than it’s parent.
  2. If the current node is the right child of its parent, then it must have a value larger than its parent and it also needs to pass down it’s value to the left subtree so that none of the nodes in its left subtree is less than its parent.

For a more clear picture, have a look at the code.

#include <bits/stdc++.h>

using namespace std;

struct Node{
  Node* left;
  Node* right;
  int data;
};

Node* createNode(int key){
    Node* temp = new Node();
    temp->data = key;
    temp->right = nullptr;
    temp->left = nullptr;
    return temp;
}

Node* root = nullptr;

Node* insertNode(Node* node, int key){
    Node* temp = createNode(key);
    if(root == nullptr){
        root = temp;
        return root;
    }
    if(node == nullptr){
        return temp;   
    }
    
    if(key < node->data){
        node->left = insertNode(node->left, key);
    }else if(key > node->data){
        node->right = insertNode(node->right, key);
    }
    return node;
}

void levelOrderTraversal(){
    Node* temp = root;
    queue<Node*> q;
    q.push(temp);
    while(!q.empty()){
        Node* front = q.front();
        cout<<front->data<<" ";
        q.pop();
        if(front->left != nullptr){
            q.push(front->left);
        }
        if(front->right != nullptr){
            q.push(front->right);
        }
    }
}

bool helper(Node* node, long long lower, long long upper){
    if(node == nullptr){
        return true;
    }
    return (node->data > lower) && (node->data < upper) && helper(node->right, node->data, upper) && helper(node->left, lower, node->data); 
}

bool isValidBST(Node* root) {
    return helper(root, LLONG_MIN, LLONG_MAX);
}

int main()
{
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 10);
    insertNode(root, 1);
    insertNode(root, 6);
    insertNode(root, 14);
    insertNode(root, 4);
    insertNode(root, 7);
    insertNode(root, 13);
    levelOrderTraversal();
    cout<<endl;
    if(isValidBST(root)){
    	cout<<"It is a valid BST";
    }else{
    	cout<<"It's not a valid BST";
    }
    return 0;
}

Also, take a look at another popular interview problem Least Common Ancestor.

One comment

Leave a Reply

Your email address will not be published.