Validate Binary Search Tree

LeetCode 98 | Difficulty: Medium

Medium

Problem Description

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.

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:

- The number of nodes in the tree is in the range `[1, 10^4]`.

- `-2^31 <= Node.val <= 2^31 - 1`

Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

---

Approach

Tree DFS

Traverse the tree recursively (or with a stack). At each node, decide: what information do I need from the left/right subtrees? Process: go left → go right → combine results. Consider preorder, inorder, or postorder traversal based on when you need to process the node.

When to use

Path problems, subtree properties, tree structure manipulation.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	11.6 MB
Date	2018-12-26

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return IsValidBST(root, Int64.MinValue, Int64.MaxValue);

}
private bool IsValidBST(TreeNode root, Int64 min, Int64 max)
{
    if(root==null) return true;
    else return
    root.val > min
    && root.val < max
    && IsValidBST(root.left, min, root.val)
    && IsValidBST(root.right, root.val, max);
    
}
}

📜 1 more C# submission(s)

Submission (2018-01-11) — 212 ms, N/A

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return IsValidBST(root, Int64.MinValue, Int64.MaxValue);

}
private bool IsValidBST(TreeNode root, Int64 min, Int64 max)
{
    if(root==null) return true;
    else return
    root.val > min
    && root.val < max
    && IsValidBST(root.left, min, root.val)
    && IsValidBST(root.right, root.val, max);
    
}
}

---

Complexity Analysis

Approach	Time	Space
Tree Traversal	$O(n)$	$O(h)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.