You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:
A large-scale platform stores ordered data such as:
- user IDs in access control systems
- product prices in a marketplace cache
- ranked scores in a recommendation index
- time-series keys in a storage engine
To support fast range queries and efficient lookups, the system uses a Binary Search Tree (BST) as an in-memory index.
Before running a migration, enabling a feature flag, or trusting the index for queries, the platform must verify that the tree structure is a valid BST. A single corrupted pointer or bad insertion can break the ordering guarantees and cause incorrect search results.
This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.
Your Task
Given the root of a binary tree, determine if it is a valid Binary Search Tree.
A BST is valid if:
- For every node, all values in the left subtree are strictly less than the node’s value
- For every node, all values in the right subtree are strictly greater than the node’s value
- Both left and right subtrees must also be valid BSTs
Note: Duplicates are not allowed in a strict BST.
Input Format
root: the root node of a binary tree
Each node is defined as:
TreeNode { int val; TreeNode left; TreeNode right; }
Output Format
- A boolean value
true if the tree is a valid BSTfalse otherwise
Examples
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: Node 3 is in the right subtree of 5, but 3 < 5, so BST ordering is violated.
Example 3:
Input: root = [1,1]
Output: false