Check is a BT is BST or not

Problem Overview

The problem "Validate Binary Search Tree" is a classic algorithm problem that asks us to determine whether a given binary tree is a valid binary search tree (BST). This problem is commonly faced by software engineers to understand fundamental data structure concepts such as trees and recursion. The official problem statement can be accessed here.

Understanding the Problem

In a Binary Search Tree (BST), every node follows a specific ordering property:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Given a binary tree, we need to check if it adheres to the conditions of a BST. This requires a recursive or iterative traversal of the tree while maintaining constraints on the allowable values at each node.

Key DSA Concepts and Theory

Before diving into the solution, let’s revisit some key concepts:

Binary Tree

A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child.

Binary Search Tree (BST)

A BST is a special type of binary tree that maintains order:

• Left subtree contains values less than the parent node.
• Right subtree contains values greater than the parent node.

Inorder Traversal

Inorder traversal of a BST produces a sorted sequence. This property can be utilized to validate the BST structure by ensuring the sequence is strictly increasing.

Solution Approach

To solve this problem, we can either perform an inorder traversal to check the sorted order of the values or use recursion by propagating the range constraints:

Recursive Range Check

1. Start at the root node of the tree.
2. Pass down the allowable range for each node.
3. At each node, check if its value falls within the permissible range.
4. Update the permissible range for the left and right subtrees accordingly.
5. If all nodes meet their constraints, the tree is a valid BST.

Below are the implementations in C++ and Java.

C++ Code

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }
    
    bool validate(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) {
        if (!node) return true;
        if ((minNode && node->val <= minNode->val) || 
            (maxNode && node->val >= maxNode->val))
            return false;
        return validate(node->left, minNode, node) && 
               validate(node->right, node, maxNode);
    }
};

Java Code

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }
    
    private boolean validate(TreeNode node, TreeNode minNode, TreeNode maxNode) {
        if (node == null) return true;
        if ((minNode != null && node.val <= minNode.val) || 
            (maxNode != null && node.val >= maxNode.val))
            return false;
        return validate(node.left, minNode, node) && 
               validate(node.right, node, maxNode);
    }
}

Time and Space Complexity Analysis

• Time Complexity: The time complexity is O(n), where n is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case, the height can be O(n) for a completely unbalanced tree.

Common Mistakes to Avoid

1. Confusing Node Values: Remember that the constraints for the left child are not just less than the parent, but within a specific range defined by its ancestors.
2. Neglecting Null Checks: Always check if a node is null to avoid null pointer exceptions.
3. Using Incorrect Data Types: Be cautious with data types, especially with large integer values to avoid overflow issues.

Similar Problems on LeetCode

• BST Iterator (Problem 173)
• Balancing a BST (Problem 1382)
• Convert Sorted Array to BST (Problem 108)

Additional Resources and References

• Binary Trees and BSTs – GeeksforGeeks
• Recursion, DFS, and in-order traversal explanations on StackOverflow

This problem and its variations are essential for mastering binary trees and understanding recursion in depth, equipping you with foundational skills for tackling more complex data structures.