Check if Binary Tree is BST

Problem Statement: You are given the root of a binary tree. The task is to determine if the given binary tree qualifies as a binary search tree.

Conditions for a Binary Tree to qualify as Binary Search Tree (BST):

  • The left child’s key is less than the key of its parent.
  • The right child’s key is more than the key of its parent.
  • The left and right subtrees also count as BST individually.

Example 1:

Input: Address of root node given

Output: True

Explanation: Since the above Binary tree obeys all the conditions of BST return true.

Example 2:

Input: Address of root node given.

Output: False

Explanation: The root contains key 7, hence its left subtree should have nodes containing a key less than 7 but there is a node having its key as 9. This violates the principle of BST.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Pre-requisites: Recursion, Tree traversal techniques

Solution 1: 

Initial thoughts: Let us assume we have a node X. To check for BST, X’s key should not only be compared with its immediate left and right children but also its entire left and right subtree. So checking the entire left and right subtree for every node in a tree will be very inefficient.

Approach: The efficient method to solve this problem in a single traversal is discussed below:-

  • Before visiting every node, a range is assigned to it. The lower bound and upper bound of the range is passed as parameters to the function. 
  • While visiting the node observe if the node’s key lies between the upper and lower bound.
    • If not, return a false without any further traversal.
    • If yes, make recursion calls once for the left subtree and right subtree of the node.
  • Once we reach null, return true. 

NOTE: The lower bound of the starting range is a minimum integer, say INT_MIN, and the upper bound is a maximum integer, say INT_MAX because the root’s key can have any value.

Have a look at the dry run for a better understanding.

  • Start with root(key = 7) and the said initial range. INT_MIN < 7 < INT_MAX. Continue traversal.
  • Arrive at node with key 5 with [INT_MIN,7] as range.INT_MIN < 5 < 7.Continue traversal.
  • Arrive at a node with key 3 with  [INT_MIN, 5] as a range. INT_MIN < 3 < 5. Continue traversal.
  • Reaches NULL. Return true.
  • Arrive at the node with key 6 with  [5, 7] as a range. 5 < 6 < 7. Continue traversal.
  • Reaches NULL. Return true.
  • Arrive at a node with key 10 with  [7, INT_MAX] as the range. 7 < 10 < INT_MAX. Continue traversal.
  • Arrive at a node with key 4 with  [7, 10] as the range. 4 does not lie in the range. Do not continue traversal, return false.

Code:

C++ Code

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

struct Node {
    int data;
    Node * left, * right;
    Node(int val) {
        data = val;
        left = NULL;
        right = NULL;
    }
};
class Solution {
    public:
        bool isValidBST(Node * root) {
            return solve(root, INT_MIN, INT_MAX);
        }

    bool solve(Node * root, int minVal, int maxVal) {
        if (root == NULL) return true;
        if (root -> data >= maxVal || root -> data <= minVal) return false;
        return solve(root -> left, minVal, root -> data) && solve(root -> right, 
        root -> data, maxVal);
    }
};
int main() {
    Node * root = new Node(7);
    root -> left = new Node(5);
    root -> left -> left = new Node(3);
    root -> left -> right = new Node(6);
    root -> right = new Node(10);
    root -> right -> left = new Node(4);
    root -> right -> right = new Node(15);
    Solution ob;
    bool ans = ob.isValidBST(root);
    if (ans == true) {
        cout << "Valid BST";
    } else {
        cout << "Invalid BST";
    }
    return 0;
}

Output: Invalid BST

Time Complexity: O(N) for traversing N nodes.

Space Complexity: O(1) if we ignore the auxiliary stack space.

Java Code

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Node root = new Node(7);
        root.left = new Node(5);
        root.left.left = new Node(3);
        root.left.right = new Node(6);
        root.right = new Node(10);
        root.right.left = new Node(9);
        root.right.right = new Node(15);
        Solution ob = new Solution();
        boolean ans = ob.isValidBST(root);
        if (ans == true) {
            System.out.print("Valid BST");
        } else {
            System.out.print("Invalid BST");
        }
    }

}

class Node {
    int data;
    Node left, right;
    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}
class Solution {
    private boolean checkBST(Node node, long min, long max) {
        if (node == null) return true;
        if (node.data <= min || node.data >= max) return false;

        if (checkBST(node.left, min, node.data) && checkBST(node.right, node.data, 
        max))
       {
            return true;
        }
        return false;
    }
    public boolean isValidBST(Node root) {
        return checkBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
}

Output: Valid BST

Time Complexity: O(N) for traversing N nodes.

Space Complexity: O(1) if we ignore the auxiliary stack space.

Special thanks to Somparna Chakrabarti for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article