Check if BST is Valid in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

    

C Program

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct N { int d; struct N *l, *r; } N;
N* n(int d) { N* t = malloc(sizeof(N)); t->d = d; t->l = t->r = NULL; return t; }
int isBST(N* r, int min, int max) {
    if (!r) return 1;
    if (r->d <= min || r->d >= max) return 0;
    return isBST(r->l, min, r->d) && isBST(r->r, r->d, max);
}
int main() {
    N *r = n(10);
    r->l = n(5); r->r = n(15);
    r->r->l = n(6); // violates BST
    printf("%s", isBST(r, INT_MIN, INT_MAX) ? "Valid" : "Invalid");
}

C Output

Input:  
      10
     /  \
    5    15
         /
        6

Output:  
Invalid

C++ Program

#include <iostream>
#include <climits>
using namespace std;
struct N { int d; N *l, *r; N(int v): d(v), l(0), r(0) {}; };
bool isBST(N* r, int min, int max) {
    if (!r) return true;
    if (r->d <= min || r->d >= max) return false;
    return isBST(r->l, min, r->d) && isBST(r->r, r->d, max);
}
int main() {
    N* r = new N(20);
    r->l = new N(10); r->r = new N(30);
    r->r->l = new N(25);
    cout << (isBST(r, INT_MIN, INT_MAX) ? "Valid" : "Invalid");
}

C++ Output

Input:  
       20
      /  \
    10    30
         /
       25  

Output:  
Valid

JAVA Program

class N {
    int d; N l, r;
    N(int d) { this.d = d; }
}
public class Main {
    static boolean isBST(N r, int min, int max) {
        if (r == null) return true;
        if (r.d <= min || r.d >= max) return false;
        return isBST(r.l, min, r.d) && isBST(r.r, r.d, max);
    }
    public static void main(String[] a) {
        N r = new N(5);
        r.l = new N(3); r.r = new N(8);
        r.l.l = new N(1); r.l.r = new N(4);
        System.out.println(isBST(r, Integer.MIN_VALUE, Integer.MAX_VALUE) ? "Valid" : "Invalid");
    }
}

JAVA Output

Input:  
        5
       / \
      3   8
     / \
    1   4 

Output:  
Valid

Python Program

class N:
    def __init__(s, d): s.d, s.l, s.r = d, None, None
def isBST(r, mn, mx):
    if not r: return True
    if not (mn < r.d < mx): return False
    return isBST(r.l, mn, r.d) and isBST(r.r, r.d, mx)

r = N(10)
r.l = N(5); r.r = N(15)
r.r.l = N(12); r.r.r = N(18)
print("Valid" if isBST(r, float('-inf'), float('inf')) else "Invalid")

Python Output

Input:  
        10
       /  \
      5    15
          /  \
        12    18  

Output:  
Valid

In-Depth Explanation

Example

Take the Java example. The tree is:

        5
       / \
      3   8
     / \
    1   4

All nodes follow the BST rule:

• Left child < parent

• Right child > parent
  So it's Valid.

In the C example, node 6 is incorrectly placed in the right subtree of 10 but is smaller than 10. That breaks the rule → Invalid.

Real-Life Analogy

Imagine organizing books in a library shelf:

• Left shelf = books with names before 'M'

• Right shelf = books with names after 'M'

If someone puts a book named "Apple" in the "Z" section, that ruins the structure — just like inserting a wrong node in a BST.

Why It Matters

Validating a BST is important to:

• Ensure sorted data operations work efficiently (O(log n))

• Maintain data integrity in databases, memory trees, or indexes

• Detect corruption or wrong insertions in tree-based structures

Learning Insights

You learn:

• Recursive range checking: each node must lie within bounds defined by its ancestors

• Why “just checking left < root < right” is not enough — you must check for all descendants

• How to write recursive base and boundary cases cleanly

This builds skills in recursion, range validation, and memory-efficient tree traversal — core skills for any coder.

Interview & Real-World Use

This is a favorite interview question because:

• It tests recursion deeply

• Simple-looking but tricky in logic

• Requires correct understanding of BST properties

In real-world projects, it's used in:

• Validating in-memory data indexes

• Rechecking corrupted structures

• Ensuring AVL, Red-Black, and B-trees are correctly built

• Tree-structured JSON/XML validation

Checking whether a binary tree is a valid BST is a classic algorithm that reveals deep understanding of recursion, constraints propagation, and binary tree logic. The clean, short, and fully working codes above in C, C++, Java, and Python make this concept easy to grasp. This skill is vital in interviews, and in building or debugging any real-world application involving search trees, databases, or hierarchical systems.