# The Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

- 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.

# Notes:

- Note that a valid BST should have ALL node in the left less than the root (of each level), not only the immediate left child. This impose a min-max constraint of all the nodes other than top root.
- In the recursion, it also pass that min-max constraint from top to bottom. In each recursion it checks left and right node not only valid for their parent (left < root < right), but also check if they are in the min-max range (The range is built up by all their ancestors).

# Java Solution

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isValidBST(TreeNode root){ return isValid(root Integer.MIN_VALUE, Integer.MAX_VALUE) ; } private boolean isValid(TreeNode root, int min, int max){ if(root==null) return true; if(root.val <= min || root.val >= max) return false; return isValid(root.left, min, root.val) && isValid(root.right, root.val, max); } }

Advertisements