[[Binary trees and Binary search trees]]

Problem

Given a binary tree validate that its a binary search tree

A valid BST is defined as follows:

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

. 2
 /. \
1.  3
   
Valid tree

Brain storming

Initial idea is node.left.data <= node.data and node.data <= node.right.data. a simple check across the traversal would ideally work if at each level we just do this check , but here in lies the key problem.

.     10
     /  \
    5    20
        /
       6

In the above tree the local checks will validate for all the nodes for eg at root it will check and give true for node.left.data(5) <= node.data(10) <= node.right.data(20) and then at the next level also give a true for node.left(6) <= node.data(20) but globally this check is failing as 6 is < 10 but it is on the right side of the tree

This means our rule is not just local. The BST property is global. A more accurate way to say it is:

• Everything in a node’s left subtree must be <= node.data.
• Everything in a node’s right subtree must be >= node.data.

This gives us a new idea. When our function is at a specific node, it’s not enough to know about its immediate parent. It needs to know about the constraints placed on it by all of its ancestors.

This is the core insight! As we traverse down the tree, we carry with us a valid range (a lower_bound and an upper_bound) that every node in the current subtree must obey.

A key takeaway learned from [[Binary Tree is height balanced?]] is that an empty node is a valid balanced binary tree and a valid binary search tree

so the base case of node being None will be True

the recurse helper be is_bst_helper(node, lower_bound, upper_bound)

1. The algorithm will start we will first check for the current node (pre order traversal root , left , right)
2. check if lower_bound <= node.data <= upper_bound. if it passes this then the node.data becomes the upper bound for the left tree and the lower bound for the right tree
3. is_left_bst = is_bst_helper(node.left, lower_bound, node.data) is_right_bst = is_bst_helper(node.right, node.data, upper_bound)
4. then return the union of left and right return is_left_bst and _is_right_bst

for initialisation we will us float('inf') and -float('inf')

below is the python implementation

class TreeNode: 
	def __init__(self, val=0, left=None, right=None): 
	self.val = val 
	self.left = left 
	self.right = right

def is_bst_helper(node:TreeNode, min_bound = -float('inf'), max_bound= float('inf')):
	if node is None:
		return True
	
	if not min_bound <= node.data <= max_bound:
		return False
		
	else:
		is_left_bst = is_bst_helper(node.left, min_bound, node.data)
		is_right_bst = is_bst_helper(node.right, node.data, max_bound)
		return is_left_bst and is_right_bst