Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
[1, 104].-231 <= Node.val <= 231 - 1To solve Validate Binary Search Tree, the key idea is understanding the core BST rule: every node must be greater than all values in its left subtree and smaller than all values in its right subtree. A simple comparison with immediate children is not enough because violations can occur deeper in the subtree.
A common approach uses Depth-First Search (DFS) while maintaining a valid value range for each node. When traversing left, the upper bound becomes the current node's value; when traversing right, the lower bound becomes the current node's value. If any node breaks these constraints, the tree is not a valid BST.
Another intuitive method relies on inorder traversal. Since the inorder sequence of a BST should produce a strictly increasing list of values, you can track the previously visited value and ensure the current value is always greater.
Both strategies visit each node once, resulting in efficient performance with recursion stack space proportional to the tree height.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Min/Max Bounds | O(n) | O(h) |
| Inorder Traversal Check | O(n) | O(h) |
NeetCode
This approach involves recursively traversing the binary tree in an in-order manner, comparing each node's value with a running minimum and maximum valid value, to ensure the BST properties hold. The initial minimum and maximum allow for any integer value, and they get updated as we traverse the tree.
Time Complexity: O(n), where n is the number of nodes because we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursive stack usage.
1#include <limits.h>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11public:
12 bool validate(TreeNode* node, long min, long max) {
13 if (!node) return true;
14 if (node->val <= min || node->val >= max) return false;
return validate(node->left, min, node->val) &&
validate(node->right, node->val, max);
}
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
};The method validate performs a similar function as in C. It checks the current node's validity and calls itself for left and right subtrees with updated constraints.
This approach involves an iterative in-order traversal using a stack to ensure non-decreasing order of node values. We iterate through the nodes using the stack and at each step, compare the current node's value with the last visited node.
Time Complexity: O(n) since each node is visited once.
Space Complexity: O(h) for the stack where h is tree height.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In a valid Binary Search Tree, an inorder traversal produces values in strictly increasing order. By tracking the previously visited value and ensuring the current value is always greater, you can detect violations efficiently.
Yes, this problem is frequently asked in technical interviews at FAANG and other top tech companies. It tests understanding of binary trees, recursion, and the properties of Binary Search Trees.
The optimal approach uses Depth-First Search while maintaining valid minimum and maximum bounds for each node. During traversal, every node must fall within its allowed range. If any node violates the constraint, the tree is not a valid BST.
Depth-First Search with recursion is the most common technique. It allows you to propagate valid value ranges or track previous values during inorder traversal while visiting each node exactly once.
This solution uses a manual stack (implemented as a struct in C) to perform in-order traversal. We keep track of the previous node's value to ensure all nodes are in increasing order.