Validate Binary Search Tree | Dataford Interview Questions

Your question is Validate Binary Search Tree. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

At Dropbox, a service stores ordered values in a binary tree and needs to verify that the structure satisfies binary search tree rules. Given the root of a binary tree, implement a function that returns True if it is a valid binary search tree (BST), otherwise return False.

A valid BST must satisfy all of the following:

Every node in the left subtree contains a value strictly less than the current node's value.
Every node in the right subtree contains a value strictly greater than the current node's value.
Both left and right subtrees must also be valid BSTs.

Formal Specification

Input: root, the root node of a binary tree represented as nested dictionaries or null.
Output: A boolean indicating whether the tree is a valid BST.

Constraints

The number of nodes is in the range [0, 10^4]
-2^31 <= node.val <= 2^31 - 1
Each node has fields: val, left, and right
A valid BST requires strict ordering: left < node < right

Function Signature

def is_valid_bst(root=None, **kwargs):