Validate Binary Search Tree
The key idea
A node is not just greater than its parent or smaller than it. Every node must fall inside a range fixed by all of its ancestors. Pass a low and high bound down the tree, or do an in-order walk and check the values come out strictly increasing.
Problem
Given the root of a binary tree, decide whether it is a valid binary search tree (BST).
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, and both the left and right subtrees must themselves also be valid binary search trees.
Return true if the tree is a valid BST, and false otherwise.
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. -2^31 <= Node.val <= 2^31 - 1
Examples
Input: root = [2,1,3]
Output: true
Input: root = [5,1,4,null,null,3,6]
Output: false
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY