Validate Binary Search Tree - Practice Coding Problems

Validate Binary Search Tree - Problem

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.

Input & Output

Example 1 — Valid BST

$ Input: root = [2,1,3]

› Output: true

💡 Note: The tree is a valid BST: left child 1 < root 2 < right child 3, and all subtrees are valid BSTs

Example 2 — Invalid BST

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

› Output: false

💡 Note: The right subtree contains 3 which is less than root 5, violating BST property

Example 3 — Single Node

$ Input: root = [1]

› Output: true

💡 Note: A single node is always a valid BST

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-2³¹ ≤ Node.val ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes and values

BST Rules

Left < Root < Right for all nodes

Validation

Check if all nodes follow BST property

Key Takeaway

🎯 Key Insight: Use min/max bounds to validate each node's position relative to its ancestors

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The optimal approach uses DFS with min/max bounds to validate each node in a single pass. Each node must satisfy range constraints inherited from its ancestors. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ Inorder Traversal	O(n)	O(h)	Perform inorder traversal and check if values are in strictly increasing order
DFS with Min/Max Bounds	O(n)	O(h)	Use depth-first search with min/max bounds to validate each node in one pass
Brute Force - Check All Nodes	O(n²)	O(h)	For each node, verify all left subtree nodes are smaller and all right subtree nodes are larger

Inorder Traversal — Algorithm Steps

Perform inorder traversal of the tree
During traversal, check if current value > previous value
Return false if any value violates increasing order
Return true if all values are in order

Visualization

Tap to expand

Step-by-Step Walkthrough

Inorder Path

Left → Root → Right traversal

Check Order

Each value must be > previous

Validation

Sorted sequence confirms valid BST

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct TreeNode* prev = NULL;

bool inorder(struct TreeNode* node) {
    if (!node) return true;
    
    if (!inorder(node->left)) return false;
    
    if (prev && node->val <= prev->val) {
        return false;
    }
    
    prev = node;
    
    return inorder(node->right);
}

bool solution(struct TreeNode* root) {
    prev = NULL;
    return inorder(root);
}

int main() {
    // Simplified parsing for demo
    struct TreeNode* root = createNode(2);
    root->left = createNode(1);
    root->right = createNode(3);
    
    bool result = solution(root);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during inorder traversal

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

67.8K Views

High Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Inorder Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler