How to validate a Binary Search Tree | Importance and algorithm | Leetcode

Why Do we Care about Binary Search Tree?

It's a fundamental building block for databases and data structures used in Big Tech, Common interview question at tech companies, especially when discussing optimisation.

BST validation is crucial because BSTs are used for efficient searching/sorting (O(log n) operations). Invalid BSTs break these performance guarantees.

If we use Binary search Tree(BST) frequently then there should at least be validation put to check if a binary search tree is valid as it claims to be.

Real-world impact: Database indexes (B-trees) rely on BST properties.

Invalid trees = incorrect/slow queries.

An example of BST is Youtube organising it's content hierarchically for recommendation and search indexing

                2
            1       3

leftSubtree of 2 is smaller than 2 and rightSubTree of 2 is greater than 2

left subtree of every node contains only nodes with keys less than the node's key

Valid Binary Search Tree

Given the root of a binary tree, return true if it is a valid binary search tree, otherwise return false.

A valid binary search tree satisfies the following constraints:

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

Example 1:

Input: root = [2,1,3]

Output: true

Example 2:

Input: root = [1,2,3]

Output: false

Explanation: The root node's value is 1 but its left child's value is 2 which is greater than 1.

Constraints:

• 1 <= The number of nodes in the tree <= 1000.
• -1000 <= Node.val <= 1000

Let's see how we'd validate a binary search tree manually, let's observe a pattern there.

                        20
                15                 35
            10        18        24          40
          4   12    16  19    23   26     38  45   

20 -> 15, 15 is less than 20
15 -> 10, 10 is less than 15
10 -> 4,  4 is less than 10

1. but what should the 15 be greater than or the upper bound
2. what should 10 be greater than?
3. what should 4 be greater than?

it is greater than a random number, cause we don't care

On Traversing Left

node -> newNode

random? < newNode && newNode < node 

                        20
                15                 35
            10        18        24          40
          4   12    16  19    23   26     38  45   

On Traversing Right

20 -> 35, this new 35 node should be greater than 20
35 -> 40, this new node 40 should be greater than 35
40 -> 45. this new node 45 should be greater than 45?

we see a pattern this

node < newNode

but what should it be smaller than?

that we don't care,

node < newNode  && newNode < random

here we see a pattern, that anytime we go right, we update our left boundary and anytime we go left, we update our right boundary

function inRange(min, value, max){
  return min < value && value < max
}

// next i want to do a traversal
function inorder(node, leftBoundry, rightBoundry){
 if(!node){
    return true
 }
 if(!inRange(leftBoundry, node.val, rightBoundry)){
   return false
 }
 return inorder(node.left, leftBoundry, node.val) && inorder(node.right, node.val, rightBoundry) 
}

 return inorder(root, -Infinity, Infinity)

#binarySearchTree #dataStructure #leetcode