LogoKode$word

LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained

Learn how to solve LeetCode 98 Validate Binary Search Tree using recursion and min/max bounds in Java. Includes BST intuition, brute force approach, optimized DFS solution, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
0 views
LinkedInGithubX
0
0
LeetCodeBinary Search TreeBSTJavaDFS TraversalBinary TreeRecursionMedium
LeetCode 98: Validate Binary Search Tree – Java DFS Recursive Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 98 – Validate Binary Search Tree is one of the most important Binary Search Tree interview problems.

This question is extremely popular because it tests:

  1. BST properties
  2. Recursive tree traversal
  3. DFS recursion
  4. Range validation
  5. Tree constraints handling

Many beginners make mistakes on this problem because checking only parent-child relationships is not enough.

Understanding the correct BST validation logic is very important for interviews.

Problem Link

🔗 https://leetcode.com/problems/validate-binary-search-tree/

Problem Statement

Given the root of a binary tree, determine whether it is a valid Binary Search Tree (BST).

A valid BST follows:

  1. Left subtree contains only smaller values
  2. Right subtree contains only greater values
  3. Both left and right subtrees must also be BSTs

Example 1

Input

root = [2,1,3]

Output

true

Explanation

2
/ \
1 3

All BST conditions are satisfied.

Example 2

Input

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

Output

false

Why False?

5
/ \
1 4
/ \
3 6

Although:

4 < 6

the node:

4

exists inside the right subtree of:

5

and should therefore be greater than 5.

This violates BST rules.

Key Insight

The most important understanding:

Every node must satisfy an entire valid range, not just parent comparison.

This is where many incorrect solutions fail.

Common Wrong Thinking

Many beginners try:

if(root.left.val < root.val && root.right.val > root.val)

This is incorrect.

Because BST validation depends on:

ALL ancestor constraints

not just immediate parent.

Correct Intuition

Each node has:

  1. Minimum allowed value
  2. Maximum allowed value

For example:

Left subtree -> values smaller than root
Right subtree -> values greater than root

As recursion goes deeper:

constraints become tighter

Visual Understanding

10
/ \
5 15
/ \
6 20

Node:

6

is invalid because:

6 < 10

even though:

6 < 15

This proves:

Parent-only checking is insufficient.

Brute Force Approach

Idea

For every node:

  1. Find maximum in left subtree
  2. Find minimum in right subtree
  3. Validate BST conditions

Brute Force Complexity

Time Complexity

O(N²)

Because subtree traversal repeats for every node.

Space Complexity

O(H)

Recursive stack space.

Optimized Recursive DFS Approach

The optimized idea:

Pass valid range during recursion.

Each node must satisfy:

min < node.val < max

Java Solution

class Solution {

public boolean solve(TreeNode root, long min, long max) {

if(root == null) return true;

if(root.val <= min || root.val >= max) {
return false;
}

return solve(root.left, min, root.val)
&& solve(root.right, root.val, max);
}

public boolean isValidBST(TreeNode root) {

if(root == null) return true;

return solve(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}

Why Use Long Instead of Int?

Constraints allow:

-2³¹ <= Node.val <= 2³¹ - 1

Using:

Integer.MIN_VALUE
Integer.MAX_VALUE

can create edge-case failures.

So we safely use:

Long.MIN_VALUE
Long.MAX_VALUE

How This Works

For every node:

Left Subtree

Allowed range:

(min, root.val)

Right Subtree

Allowed range:

(root.val, max)

This guarantees global BST validity.

Dry Run

Input

root = [2,1,3]

Step 1

Current node:

2

Allowed range:

(-∞, +∞)

Valid.

Step 2

Move left:

1

Allowed range:

(-∞, 2)

Valid.

Step 3

Move right:

3

Allowed range:

(2, +∞)

Valid.

Final Output

true

Another Dry Run

Input

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

Step 1

Node:

5

Range:

(-∞, +∞)

Valid.

Step 2

Move right to:

4

Range:

(5, +∞)

Now:

4 <= 5

Invalid BST.

Final Output

false

Time Complexity Analysis

Time Complexity

O(N)

Every node visited once.

Space Complexity

O(H)

Where:

H = height of tree

Worst case:

O(N)

for skewed tree.

Alternative Approach Using Inorder Traversal

Key Property

BST inorder traversal produces:

strictly increasing order

Inorder Java Solution

class Solution {

TreeNode prev = null;

public boolean inorder(TreeNode root) {

if(root == null) return true;

if(!inorder(root.left)) return false;

if(prev != null && root.val <= prev.val) {
return false;
}

prev = root;

return inorder(root.right);
}

public boolean isValidBST(TreeNode root) {
return inorder(root);
}
}

Interview Explanation

In interviews, explain:

A valid BST requires every node to satisfy ancestor constraints, not just parent constraints. Therefore, we recursively maintain valid minimum and maximum bounds for each node.

This demonstrates:

  1. Deep BST understanding
  2. Recursive DFS mastery
  3. Constraint propagation
  4. Edge-case handling

Common Mistakes

1. Comparing Only Parent Nodes

Incorrect approach:

root.left.val < root.val

This misses ancestor violations.

2. Forgetting Strict Inequality

BST requires:

strictly smaller
strictly greater

Duplicates are invalid.

3. Using int Instead of long

Can fail on edge values.

Always use:


long min
long max

4. Incorrect Range Passing

Correct recursion:

left -> (min, root.val)
right -> (root.val, max)

FAQs

Q1. Why does parent comparison fail?

Because BST validity depends on all ancestor constraints.

Q2. Why use min/max bounds?

Bounds propagate BST restrictions correctly.

Q3. Can inorder traversal solve this?

Yes.

BST inorder traversal must be strictly increasing.

Q4. Is this asked frequently?

Very frequently.

It is one of the most important BST interview questions.

Related Problems

Practice these next:

  1. Search in BST
  2. Insert into BST
  3. Lowest Common Ancestor in BST
  4. Kth Smallest Element in BST

Conclusion

LeetCode 98 is an excellent problem for mastering:

  1. BST validation
  2. Recursive DFS
  3. Constraint propagation
  4. Tree traversal
  5. Interview problem-solving

The key insight is:

Every BST node must satisfy a valid global range, not just local parent conditions.

Once this concept becomes intuitive, many advanced BST problems become significantly easier.

Related Articles

LeetCode 701: Insert into a Binary Search Tree – Java Recursive Solution with Dry Run

LeetCode 701: Insert into a Binary Search Tree – Java Recursive Solution with Dry Run

Learn how to solve LeetCode 701 Insert into a Binary Search Tree using recursion in Java. Includes BST intuition, brute force approach, optimized recursive solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Inorder Successor in BST – Java Optimized BST Solution with Dry Run

Inorder Successor in BST – Java Optimized BST Solution with Dry Run

Learn how to solve the GFG Inorder Successor in BST problem using optimized BST traversal in Java. Includes brute force approach, recursive BST solution, intuition, dry run, complexity analysis, interview tips, and common mistakes.

Read Article
Ceil in BST – Java Recursive Binary Search Tree Solution with Dry Run

Ceil in BST – Java Recursive Binary Search Tree Solution with Dry Run

Learn how to solve the Ceil in BST problem using an optimized recursive BST approach in Java. Includes intuition, brute force method, optimized recursion, dry run, time complexity, interview explanation, and common mistakes.

Read Article
LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 94 Binary Tree Inorder Traversal using Recursive and Iterative approaches in Java. Includes tree traversal intuition, dry run, stack-based solution, complexity analysis, interview tips, and common mistakes.

Read Article
Ai Assistant Kas