Validate Binary Search Tree
Problem Statement
Given the root of a binary tree, determine if 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 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.
Constraints:
- The number of nodes in the tree is in the range [1, 10^4]
- -2^31 <= Node.val <= 2^31 - 1
Input Format:
- The root of a binary tree
Output Format:
- Return true if the given tree is a valid BST, false otherwise
Examples:
Example 1:
Input:
root = [2,1,3]
Output:
true
Explanation:
The tree looks like: 2 / \ 1 3 The left subtree value 1 is less than the root value 2, and the right subtree value 3 is greater than the root value 2.
Example 2:
Input:
root = [5,1,4,null,null,3,6]
Output:
false
Explanation:
The tree looks like: 5 / \ 1 4 / \ 3 6 The value 3 is less than the root value 5, which violates the rule that all nodes in the right subtree must have values greater than the root value.
Example 3:
Input:
root = [5,4,6,null,null,3,7]
Output:
false
Explanation:
The tree looks like: 5 / \ 4 6 / \ 3 7 The value 3 is less than the root value 5, which violates the rule that all nodes in the right subtree must have values greater than the root value.
Solutions
Recursive Approach with Range Checking
Use recursion to traverse the tree, maintaining a valid range for each node. Each node's value must be within the allowable range for the tree to be a valid BST.
In-order Traversal
Perform an in-order traversal of the tree, which should yield values in ascending order for a valid BST. If at any point the current value is less than or equal to the previous value, the tree is not a valid BST.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Start validation of root node (5) with range (-Infinity, Infinity)
- Validate left subtree (1) with range (-Infinity, 5) - Valid
- Validate right subtree (4) with range (5, Infinity)
- Node value 4 is less than 5, so it's in the correct range
- Validate right subtree's left child (3) with range (5, 4)
- Node value 3 is not within range (5, 4) as 3 < 5 - Invalid
- Return false as the tree violates BST property
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the recursive validation process, showing the valid range for each node and highlighting when a node violates the BST property.
Key visualization elements:
- current node
- valid range
- violation
Similar Questions
Kth Smallest Element in a BST
MediumGiven the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Same Tree
EasyGiven the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Implementation Notes
This problem tests understanding of Binary Search Tree properties and tree traversal techniques. The key insight is recognizing that each node must be within a valid range, not just compared to its immediate children.