Log inSign up
mediumLeetCodeNot Started

Validate Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

### 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 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. - Both the left and right subtrees must also be binary search trees.

---

### Examples

Example 1: ```text 2 / \ 1 3

Input: root = [2,1,3] Output: true ```

Example 2: ```text 5 / \ 1 4 / \ 3 6

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 - The number of nodes in the tree is in the range [1, 10^4]. - -2^31 <= Node.val <= 2^31 - 1

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize why local parent-child comparison fails for BST validation.
  • Implement top-down range boundary propagation using 64-bit bounds.
  • Validate BST via inorder traversal with O(1) extra space using Morris Traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Validating binary search tree invariant
  • Need to ensure global ancestry constraints rather than local parent-child comparisons
  • Tree traversal where inorder sorted property must strictly hold

Algorithmic Decision Tree:

  • If checking BST validity -> pass allowed range (minAllowed, maxAllowed) down recursion.
  • When going left: update maxAllowed = node.val.
  • When going right: update minAllowed = node.val.
  • Or perform inorder traversal and verify prevVal < currVal.

Connected Patterns:

Recover Binary Search TreeKth Smallest Element in a BSTInorder Successor in BST

1. Subtree Max/Min Check (Bottom-Up)

Intuition

By definition, every node in left subtree must be < root, and every node in right subtree must be > root. Finding max in left and min in right for every node directly tests this property.

Algorithm

  1. Define helper findMax(root) and findMin(root).
  2. If root is null, return true.
  3. If root.left exists and findMax(root.left) >= root.val, return false.
  4. If root.right exists and findMin(root.right) <= root.val, return false.
  5. Recursively verify isValidBST(root.left) and isValidBST(root.right).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3#include <climits>
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 long long findMax(TreeNode* root) {
14 if (!root) return LLONG_MIN;
15 return std::max((long long)root->val, std::max(findMax(root->left), findMax(root->right)));
16 }
17 long long findMin(TreeNode* root) {
18 if (!root) return LLONG_MAX;
19 return std::min((long long)root->val, std::min(findMin(root->left), findMin(root->right)));
20 }
21public:
22 bool isValidBST(TreeNode* root) {
23 if (!root) return true;
24 if (root->left && findMax(root->left) >= root->val) return false;
25 if (root->right && findMin(root->right) <= root->val) return false;
26 return isValidBST(root->left) && isValidBST(root->right);
27 }
28};
29
30int main() {
31 TreeNode* root = new TreeNode(2);
32 root->left = new TreeNode(1);
33 root->right = new TreeNode(3);
34 Solution sol;
35 std::cout << "IsValidBST [2,1,3]: " << (sol.isValidBST(root) ? "true" : "false") << " (Expected: true)\n";
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(H)

2. Recursive Range Propagation (low, high)

Intuition

When traversing left, the current node becomes the upper bound. When traversing right, the current node becomes the lower bound. If any node fails low < node.val < high, the BST is invalid.

Algorithm

  1. Define helper validate(node, low, high).
  2. If node is null, return true.
  3. If node.val <= low or node.val >= high, return false.
  4. Recursively check: validate(node.left, low, node.val) && validate(node.right, node.val, high).
  5. Initial call: validate(root, -infinity, +infinity).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <climits>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x, TreeNode *l = nullptr, TreeNode *r = nullptr) : val(x), left(l), right(r) {}
9};
10
11class Solution {
12 bool validate(TreeNode* node, long long low, long long high) {
13 if (!node) return true;
14 if (node->val <= low || node->val >= high) return false;
15 return validate(node->left, low, node->val) && validate(node->right, node->val, high);
16 }
17public:
18 bool isValidBST(TreeNode* root) {
19 return validate(root, LLONG_MIN, LLONG_MAX);
20 }
21};
22
23int main() {
24 TreeNode* root = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
25 Solution sol;
26 std::cout << "IsValid [5,1,4..]: " << (sol.isValidBST(root) ? "true" : "false") << " (Expected: false)\n";
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H)

3. Morris Inorder Traversal (O(1) Space)

Intuition

Inorder traversal of a BST visits nodes in strictly increasing order. Using Morris Traversal, we thread predecessor pointers to traverse in-order without a stack or recursion, using true O(1) auxiliary space.

Algorithm

  1. Initialize curr = root, prevVal = null (or -infinity).
  2. While curr is not null:
  3. If curr.left is null:
  4. Check if prevVal != null and curr.val <= prevVal -> invalid BST.
  5. Update prevVal = curr.val.
  6. Move curr = curr.right.
  7. Else:
  8. Find inorder predecessor (rightmost node in curr.left).
  9. If predecessor.right is null: thread predecessor.right = curr, curr = curr.left.
  10. Else: remove thread predecessor.right = null. Check prevVal, update prevVal = curr.val, curr = curr.right.
  11. If traversal finishes without violation, return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12 bool isValidBST(TreeNode* root) {
13 TreeNode* curr = root;
14 TreeNode* prev = nullptr;
15 bool isValid = true;
16
17 while (curr) {
18 if (!curr->left) {
19 if (prev && curr->val <= prev->val) {
20 isValid = false;
21 }
22 prev = curr;
23 curr = curr->right;
24 } else {
25 TreeNode* pred = curr->left;
26 while (pred->right && pred->right != curr) {
27 pred = pred->right;
28 }
29
30 if (!pred->right) {
31 pred->right = curr;
32 curr = curr->left;
33 } else {
34 pred->right = nullptr;
35 if (prev && curr->val <= prev->val) {
36 isValid = false;
37 }
38 prev = curr;
39 curr = curr->right;
40 }
41 }
42 }
43 return isValid;
44 }
45};
46
47int main() {
48 TreeNode* root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
49 Solution sol;
50 std::cout << "Morris isValidBST: " << (sol.isValidBST(root) ? "true" : "false") << " (Expected: true)\n";
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Subtree Max/Min CheckO(N^2)O(H)Compare every node with the max of its left subtree and min of its right subtree.Subtree max/min repeated scans
2.Recursive Range PropagationO(N)O(H)Pass (low, high) bounds down the tree recursively.Call stack depth on skewed trees
3.Morris Inorder TraversalOptimalO(N)O(1)Thread predecessor pointers to traverse in-order with zero memory.Double traversal of threaded edges

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Comparing only node against left.val and right.val without maintaining min/max ancestor constraints.

Pitfall 2:

Using non-strict inequalities (e.g. node.val < low) allowing duplicates, which violates the strict BST definition.

Pitfall 3:

In Morris traversal, returning false immediately without clearing remaining threads, which corrupts the tree structure.

Crucial Edge Cases to Validate:

  • Node value equals INT_MIN (-2^31) or INT_MAX (2^31 - 1) — Boundaries initialized to LLONG_MIN / LLONG_MAX (or null in Java/Python) prevent false negative validations.
  • Duplicate values in tree (e.g. root=2, left=2) — Strict inequality checks (node.val <= low || node.val >= high) correctly reject duplicate keys.
  • Single node tree [1] — Trivially valid; returns true.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Immediately highlight the global vs local constraint trap on the whiteboard using tree [10, 5, 15, null, null, 6, 20] where 6 is in the right subtree of 5 but smaller than 10.
  2. Present the range propagation approach first, pointing out the 64-bit bound requirement.
  3. Mention the in-order traversal property as an alternative verification method.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it insufficient to merely check root.val > root.left.val and root.val < root.right.val?

2.What is the mathematical property of an in-order traversal of a valid BST?

3.Why should range checks use 64-bit integer limits (or null) instead of INT_MIN and INT_MAX?

Back to DSA Sheet