Skip to main content

Leetcode 98: Validate Binary Search Tree

 

1. Problem Summary


You’re given the root of a binary tree and must determine if it is a valid Binary Search Tree (BST).

A binary tree is a valid BST if for every node:

  1. All values in the left subtree are strictly less than the node’s value.

  2. All values in the right subtree are strictly greater than the node’s value.

  3. Both left and right subtrees are themselves valid BSTs.


Input: root (binary tree root, not null; up to 104 nodes)

Output: Boolean indicating whether the tree is a valid BST.


Node values can be as low as -231 and as high as 231 - 1.


2. Examples Explanation


Example 1:


Input: root = [2,1,3]

Tree:

  • 2

    • left → 1

    • right → 3

Check:

  • Left subtree of 2 has 1 < 2.

  • Right subtree of 2 has 3 > 2.

  • Subtrees rooted at 1 and 3 are leaves, so valid.

Result: true.


Example 2:


Input: root = [5,1,4,null,null,3,6]

Tree:

  • 5

    • left → 1

    • right → 4

      • left → 3

      • right → 6

Check:

  • Right child of 5 is 4, but 4 is not greater than 5 → violates BST rule at the root.

Result: false (even though 4’s internal subtree looks like a BST, the placement under 5 is invalid).


3. Approach


Pattern:


This is a tree validation problem, best solved via:

  • DFS with value bounds (top-down constraints), or

  • Inorder traversal (values must be strictly increasing).

Both are standard. The bounds method is very direct and clean.


Naive / Incorrect Approaches:


  • Only checking immediate children (e.g., node.left.val < node.val < node.right.val) is not sufficient.
    You must ensure all nodes in the left/right subtree respect constraints from all ancestors.


4. Optimal Approach 1: DFS with Min/Max Bounds (Recommended)


High-Level Idea:


For each node, we maintain a valid range (lower, upper) for its value:

  • For the root, the allowed range is (-∞, +∞).

  • When going to the left child:

    • New range: (lower, node.val) (must be strictly less than parent).

  • When going to the right child:

    • New range: (node.val, upper) (must be strictly greater than parent).

At each node:

  • If node.val <= lower or node.val >= upper → invalid.

  • Recursively validate left and right subtrees with updated bounds.

We can use long/long long or nullable bounds to avoid overflow issues with int min/max.


Key Observations:


  • This enforces constraints from all ancestors, not just the parent.

  • Time is linear in the number of nodes.

  • No extra data structures needed beyond recursion stack.


5. Alternative Approach 2: Inorder Traversal Check


For a valid BST, an inorder traversal (Left, Node, Right) must yield a strictly increasing sequence.


Algorithm:


  • Do an inorder traversal.

  • Track the value of the previously visited node.

  • If the current value is not strictly greater than the last value → invalid.

This also runs in O(n) with O(h) stack space.


Pseudo-code (Bounds-based DFS):



Complexity Analysis:


Let n be the number of nodes.

  • Time Complexity:

    • Each node is visited once.

    • O(n).

  • Space Complexity:

    • Recursion depth is at most tree height h.

    • Worst-case skewed tree: O(n); balanced: O(log n).


6. Java code



7. C code



8. C++ code



9. Python code



10. JavaScript code



Comments

Post a Comment