Decide whether a binary tree is a valid binary search tree. Every node in the left subtree must be smaller than the node, and every node in the right subtree must be bigger.
DSA Animator › DSA Revision › Tree › Validate Binary Search Tree
Remember: compare against the whole range, not just the parent. An inorder traversal that is strictly increasing is the other classic check. The video solves Validate Binary Search Tree (LeetCode 98, Medium) with the DFS with Bounds pattern from the Tree topic, and you can replay every step in the interactive Validate Binary Search Tree animation.
Decide whether a binary tree is a valid binary search tree. Every node in the left subtree must be smaller than the node, and every node in the right subtree must be bigger.
The tree 5, with children 4 and 6, where 6 has children 3 and 7, is not valid. The node 3 sits in the right subtree of 5, so it must be bigger than 5, but it is not.
The common mistake is to compare each node only with its own children. In this tree every parent child pair looks fine: 4 is less than 5, 6 is more than 5, 3 is less than 6, and 7 is more than 6. So the local check says valid, but the tree is not a search tree.
Instead, pass down a range that every node must fit inside. The root may hold any value, so its range is minus infinity to plus infinity. Going left, the node value becomes the new upper bound. Going right, the node value becomes the new lower bound. If any node falls outside its range, the tree is invalid.
The root 5 has the range minus infinity to infinity, so it fits. Its left child 4 must be below 5, and it is. Its right child 6 must be above 5, and it is. Now 3, the left child of 6, gets the range 5 to 6. The lower bound 5 came from the root, and 3 is not above 5. So the check fails, and the answer is false.
In code, the helper takes a node and two bounds, stored as long values so the integer limits are safe. A null node is valid. If the value is not strictly inside the bounds, return false. Otherwise check the left child with the upper bound set to the value, and the right child with the lower bound set to the value. Every node is checked once, so it's O of n time.
Remember: compare against the whole range, not just the parent. An inorder traversal that is strictly increasing is the other classic check.