Check if a tree is a BST or not

Intuition

To determine if a binary tree is a Binary Search Tree (BST), we need to ensure that for every node, its value falls within a specific range. This range is defined by the values of its parent nodes and their subtrees. For a node to be valid in a BST, all nodes in its left subtree must have values less than the node’s value, and all nodes in its right subtree must have values greater than the node’s value.

A straightforward way to approach this is to perform an inorder traversal of the tree, which will visit nodes in ascending order if the tree is a BST. By collecting node values in this order and then checking if this list is sorted, we can confirm whether the tree is a BST.

Approach

Define a range for each node, every node must satisfy a range of valid values. The root node is initially allowed to have any value within the range from negative infinity to positive infinity.
Start with the root node and ensure its value is within the defined range.
Recursively validate the subtrees. For the left subtree of a node, update the range to be from negative infinity to the node’s value. For the right subtree of a node, update the range to be from the node’s value to positive infinity.
Ensure that each node’s value falls within its updated range. Recursively apply the same checks to the left and right children of each node.
If all nodes satisfy their respective ranges, the tree is a BST and if any node fails the check, the tree is not a BST.

Dry Run

Solution

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

// Definition for a binary tree node.
  struct TreeNode {
      int data;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
  };
 

class Solution{
    public:
        bool isBST(TreeNode* root) {
            // Helper function to validate the BST
            return validate(root, LONG_MIN, LONG_MAX);
        }

    private:
        bool validate(TreeNode* node, long min, long max) {
            // Base case: if the node is null, return true
            if (node == nullptr) return true;
            
            // Check if the node's value falls within the valid range
            if (node->data <= min || node->data >= max) return false;
            
            // Recursively validate the left subtree
            // Update the max value to the current node's value
            bool leftIsValid = validate(node->left, min, node->data);
            
            // Recursively validate the right subtree
            // Update the min value to the current node's value
            bool rightIsValid = validate(node->right, node->data, max);
            
            // Both subtrees must be valid for the tree to be a BST
            return leftIsValid && rightIsValid;
        }
};

// Main method for testing
int main() {
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(5);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(6);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(15);
    
    Solution solution;
    std::cout << std::boolalpha << solution.isBST(root) << std::endl; // Output: false
    return 0;
}
import java.util.*;
 // Definition for a binary tree node.
  public class TreeNode {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode(int val) { data = val; left = null; right = null; }
  }
 

class Solution {
    public boolean isBST(TreeNode root) {
        // Helper function to validate the BST
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validate(TreeNode node, long min, long max) {
        // Base case: if the node is null, return true
        if (node == null) return true;
        
        // Check if the node's value falls within the valid range
        if (node.data <= min || node.data >= max) return false;
        
        // Recursively validate the left subtree
        // Update the max value to the current node's value
        boolean leftIsValid = validate(node.left, min, node.data);
        
        // Recursively validate the right subtree
        // Update the min value to the current node's value
        boolean rightIsValid = validate(node.right, node.data, max);
        
        // Both subtrees must be valid for the tree to be a BST
        return leftIsValid && rightIsValid;
    }

    // Main method for testing
    public static void main(String[] args) {
        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(5);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(6);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(15);
        
        Solution solution = new Solution();
        System.out.println(solution.isBST(root)); // Output: false
    }
}
# Definition for a binary tree node.
 class TreeNode(object):
     def __init__(self, val=0, left=None, right=None):
         self.data = val
         self.left = left
         self.right = right

class Solution:
    def isBST(self, root):
        # Helper function to validate the BST
        def validate(node, min_val, max_val):
            # Base case: if the node is None, return True
            if not node:
                return True
            
            # Check if the node's value falls within the valid range
            if node.data <= min_val or node.data >= max_val:
                return False
            
            # Recursively validate the left subtree
            # Update the max value to the current node's value
            left_is_valid = validate(node.left, min_val, node.data)
            
            # Recursively validate the right subtree
            # Update the min value to the current node's value
            right_is_valid = validate(node.right, node.data, max_val)
            
            # Both subtrees must be valid for the tree to be a BST
            return left_is_valid and right_is_valid
        
        # Initial call with the full range of values
        return validate(root, float('-inf'), float('inf'))

# Main method for testing
root = TreeNode(7)
root.left = TreeNode(5)
root.right = TreeNode(10)
root.left.left = TreeNode(3)
root.left.right = TreeNode(6)
root.right.left = TreeNode(4)
root.right.right = TreeNode(15)

solution = Solution()
print(solution.isBST(root))  # Output: False

 // Definition for a binary tree node.
  class TreeNode {
       constructor(val = 0, left = null, right = null){
           this.data = val;
           this.left = left;
           this.right = right;
       }
  }
 

class Solution {
    isBST(root) {
        // Helper function to validate the BST
        const validate = (node, min, max) => {
            // Base case: if the node is null, return true
            if (node === null) return true;
            
            // Check if the node's value falls within the valid range
            if (node.data <= min || node.data >= max) return false;
            
            // Recursively validate the left subtree
            // Update the max value to the current node's value
            const leftIsValid = validate(node.left, min, node.data);
            
            // Recursively validate the right subtree
            // Update the min value to the current node's value
            const rightIsValid = validate(node.right, node.data, max);
            
            // Both subtrees must be valid for the tree to be a BST
            return leftIsValid && rightIsValid;
        };
        
        // Initial call with the full range of values
        return validate(root, -Infinity, Infinity);
    }
}

// Main method for testing
const root = new TreeNode(7);
root.left = new TreeNode(5);
root.right = new TreeNode(10);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(6);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(15);

const solution = new Solution();
console.log(solution.isBST(root)); // Output: false

Complexity Analysis

Time Complexity O(N), Each node in the tree is visited once during the inorder traversal.

Space Complexity O(N), The recursive call stack can go up to the depth of the tree and the ans list can also store N elements in the worst case.

Problem List

Check if a tree is a BST or not

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code